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

\begin{slide}{Erreichbare und produktive Variablen}

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

Für eine CFG $G$ heißt die Variable $A$
\begin{itemize}
\item erreichbar, falls $\exists u,v\in (\Sigma\cup V)^* : S \to_R^* u A v$
\item produktiv, falls $\exists w\in \Sigma^* : A \to_R^* w$
\end{itemize}

Aufgabe: wie kann man entscheiden, ob diese Eigenschaften zutreffen
(ohne alle Ableitungen aufzuzählen)?

Vergleiche mit gleichen Begriffen
für Zustände von endlichen Automaten.

\end{slide}

\begin{slide}{Reduzierte Grammatiken}

Def: Die Grammatik $G$ heißt \emph{reduziert},

wenn alle Variablen erreichbar und produktiv sind.

Satz: zu jeder CFG $G$ gibt es eine reduzierte CGF $G'$
mit $L(G)=L(G')$.

Beweis: lösche in $G$ zuerst alle nicht produktiven Variablen,

dann alle (im Rest) nicht erreichbaren Variablen 

(jeweils mit allen Regeln, in denen  sie vorkommen)

Aufgabe: warum gerade diese Reihenfolge?
\end{slide}
