Chomsky-Normalform

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

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

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

Beweis: benutze Hilfsvariablen.

Aufgabe: Wer ist Noam Chomsky? (google)