Links-Rekursion (II)

Satz: Zu jeder CFG G gibt es CFG G' ohne Links-Rekursion mit L(G) = L(G').

Beweis (Idee): ersetze {A$ \to$Aw, A$ \to$r} durch {A$ \to$rB, B$ \to$$ \epsilon$, B$ \to$wB}.

Aufgaben (evtl. autotool): entferne Links-Rekursionen aus



Johannes Waldmann 2005-01-28