Id: epsfree.tex,v 1.1 2004/12/14 12:36:40 waldmann Exp
Def: eine CFG G heißt epsilon-frei, falls (Ar) R : r .
Bemerkung: wenn G epsilon-frei, dann L(G).
Satz: Für jede CFG G existiert eine epsilon-freie CGF G' mit L(G') = L(G) {}.
Beweis: Wende auf alle rechten Regelseiten die Substitution
A ( wenn A nullierbar, dann {A,}, sonst {A})
an, und lösche dann alle Epsilon-Regeln.
Aufgabe: Konstruiere G' für G mit R = {S | aSb | SS}.