%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\begin{slide}{Chomsky-Normalform}

\kopf{$ $Id: form.tex,v 1.1 2011-10-16 14:06:17 waldmann Exp $ $}

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

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)


\end{slide}
