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

\begin{slide}{Automaten-Synthese}

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

Satz: Zu jedem regulären Ausdruck $X$ 
gibt es einen $\epsilon$-Automaten $A$,
so daß $L(X) = L(A)$.

Beweis (\emph{Automaten-Synthese})
Wir konstruieren zu jedem $X$ ein $A$ mit:
\begin{itemize}
\item $|S(A)| = |F(A)| = 1$
\item keine Pfeile führen nach $S(A)$
\item von $S(A)$ führen genau ein Buchstaben- oder
  zwei $\epsilon$-Pfeile weg
\item keine Pfeile führen von $F(A)$ weg
\end{itemize}
Wir bezeichnen solche $A$ mit $s  \stackrel{X}{\to} f$.

\end{slide}


\begin{slide}{Automaten-Synthese (II)}

Konstruktion induktiv über den Aufbau von $X$:
\begin{itemize}\itemsep 0pt
\item für $c \in \Sigma\cup\{\epsilon\}$: $p_0 \stackrel{c}{\to} p_1$
\item für $s_X  \stackrel{X}{\to} f_X$, $s_Y \stackrel{Y}{\to} f_Ye:$ 
  \begin{itemize}\itemsep 0pt
  \item $s \stackrel {X \cdot Y}{\to} f$
    durch $s=s_X, f_X=s_Y, f_Y = f$.
  \item $s \stackrel {X + Y}{\to} f$ 
    durch $s  \stackrel{\epsilon}{\to} s_X, s  \stackrel{\epsilon}{\to} s_Y,
    f_X  \stackrel{\epsilon}{\to} f, f_Y  \stackrel{\epsilon}{\to} f$
  \item $ s \stackrel {X^*}{\to} f$
    durch $s \stackrel{\epsilon}{\to} s_X, s \stackrel{\epsilon}{\to} f,  
    f_X \stackrel{\epsilon}{\to} s_X, f_X \stackrel{\epsilon}{\to} f$.
  \end{itemize}
\end{itemize}
Satz. Der so erzeugt Automat $A$ ist korrekt. $|Q(A)| \le 2 |X|$.

\bigskip

Aufgabe:
Warum braucht man bei $X^*$ die zwei neuen Zustände $s,f$
und kann nicht $s=s_X$ oder $f=f_X$ setzen?

\bigskip

Hinweise: (wenigstens) eine der Invarianten wird verletzt,
und damit eine der anderen Konstuktionen
inkorrekt.


\end{slide}
