Id: greibachnf.tex,v 1.1 2004/12/14 12:36:40 waldmann Exp
Def: CFG G ist in Greibach-Normal-Form, falls (lr) R : r V*.
Satz: Zu jeder CFG G gibt es eine CFG G' in Greibach-NF mit L(G) {} = L(G').
Beweis ist schwer. Aber einzelne Beispiele gehen (mühsam) von Hand.
Aufgabe: finde Greibach-Nf von: