Epsilon-freie Grammatiken

Id: epsfree.tex,v 1.1 2004/12/14 12:36:40 waldmann Exp

Def: eine CFG G heißt epsilon-frei, falls $\forall$(A$\to$r) $\in$ R : r $\neq$ $\epsilon$.

Bemerkung: wenn G epsilon-frei, dann $\epsilon$ $\notin$L(G).

Satz: Für jede CFG G existiert eine epsilon-freie CGF G' mit L(G') = L(G) $\setminus$ {$\epsilon$}.

Beweis: Wende auf alle rechten Regelseiten die Substitution

A$\to$ ( wenn A nullierbar, dann {A,$\epsilon$}, sonst {A})

an, und lösche dann alle Epsilon-Regeln.

Aufgabe: Konstruiere G' für G mit R = {S$\to$$\epsilon$ | aSb | SS}.