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

\begin{slide}{Typ-3-Grammatiken und Reguläre Sprachen}

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

Def (Wdhlg): $L$ heißt regulär $\iff$
existiert regulärer Ausdruck $X$ mit $L=L(X)$.

Satz (Wdhlg): $L$ regulär $\iff$ existiert endlicher Automat $A$ 
mit $L = L(A)$. (Beweis: Analyse/Synthese)

Satz: $L$ regulär $\iff$ existiert Typ-3-Grammatik $G$ mit $L=L(G)$.
Beweis (trivial):
\begin{itemize}
\item Zustände von $A$ $=$ Variablen von $G$,
\item Startzustand von $A$ $=$ Startsymbol von $G$
\item jede Regel $p \stackrel{a}{\to} q$ in $A$ $=$ Regel $p \to aq$ in $G$
\end{itemize}

\end{slide}
