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}.



Johannes Waldmann 2006-02-02