<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">%% -*- mode: latex; TeX-master: "compilerbau.tex"; -*-

\begin{slide}{Kettenregeln}

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

Eine Regel $(l \to r)$ mit $|r|=1$ heiÃŸt \emph{Kettenregel}.

Der Ketten-AbschluÃŸ von $G$ ist die kleinste Menge $R'$ mit
\begin{itemize}
\item $R \subseteq R'$
\item falls $(A \to B) \in R$ und $(B \to r)\in R'$, dann $(A \to r)\in R'$.
\end{itemize}

Aufgaben: Wieviele Regeln kann man maximal hinzufÃ¼gen? 


Satz: Zu jeder CFG $G$
existiert eine CFG $G'$ ohne Kettenregeln 
mit  $L(G) = L(G')$.

Beweis: $G'=(\Sigma,V,S,R' ~ \mbox{ohne Kettenregeln})$.

Aufgabe: falls $R$ epsilon-frei, dann auch $R'$.


\end{slide}
</pre></body></html>