Greibach-Normalform

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

Def: CFG G ist in Greibach-Normal-Form, falls $ \forall$(l$ \to$r) $ \in$ R : r $ \in$ $ \Sigma$V*.

Satz: Zu jeder CFG G gibt es eine CFG G' in Greibach-NF mit L(G) $ \setminus$ {$ \epsilon$} = L(G').

Beweis ist schwer. Aber einzelne Beispiele gehen (mühsam) von Hand.

Aufgabe: finde Greibach-Nf von:



Johannes Waldmann 2006-02-02