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

\begin{slide}{Greibach-Normalform}

\kopf{$ $Id: greibachnf.tex,v 1.1 2011-10-16 14:06:17 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:
\begin{itemize}
\item
  $S \to TS \mid  b, T \to ST \mid a$
\item
  $S \to b \mid TT, T \to a \mid SS$
\item der Vorname von Greibach?
\end{itemize}


\end{slide}
