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

\begin{slide}{Epsilon-freie Grammatiken}

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

Def: eine CFG $G$ heißt epsilon-frei,
falls $\forall (A \to r)\in R: r \neq \epsilon$.

Bemerkung: wenn $G$ epsilon-frei, dann $\epsilon \notin L(G)$.

Satz: Für jede CFG $G$ existiert eine epsilon-freie CGF $G'$
mit $L(G') = L(G) \setminus \{\epsilon\}$.

Beweis: Wende auf alle rechten Regelseiten die Substitution 

$A \to $ ( wenn $A$ nullierbar, dann $\{A, \epsilon\}$, sonst $\{A\}$) 

an, und lösche dann alle Epsilon-Regeln.

Aufgabe: Konstruiere $G'$ für $G$ 
mit $R = \{ S \to \epsilon \mid aSb \mid SS \} $.



\end{slide}
