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

\begin{slide}{Kreise und kreisfreie Grammatiken}

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

Def: eine \emph{Kreis-Ableitung} ist von der Form $A \to_R^+ A$
für eine Variable $A$.

Satz: für jede CFG $G$ gibt es eine kreisfreie CFG $G'$
mit $L(G)=L(G')$.

Idee: $G$ epsilon-frei: $G_1$, kettenfrei: $G_2$, ist kreisfrei.

Aufgaben: 
\begin{itemize}
\item Anwenden auf $S \to \epsilon \mid SS \mid aSb$
\item Behauptung beweisen, dabei beachten:
\item wie wird $\epsilon \in L(G)$ behandelt?
\item Wie kann man entscheiden, ob gegebenes $G$ kreisfrei ist
  (ohne alle Ableitungen aufzuzählen)?
\end{itemize}

\end{slide}
