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

\begin{slide}{Automaten mit Epsilon-Übergängen}

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

Definition. Ein $\epsilon$-Automat ist \dots
mit $T \subseteq (Q \times (\Sigma \cup \{\epsilon\}) \times Q)$.

Definition.  $p \stackrel{c}{\to}_A q$ wie früher,
und $p \stackrel{\epsilon}{\to}_A q$ für $(p, \epsilon,q) \in T$.

Satz. Zu jedem  $\epsilon$-Automaten $A$
gibt es einen Automaten $B$ mit $L(A)=L(B)$.

Beweis: benutzt $\epsilon$-Hüllen: 
% $H(q) = $ alle $r \in Q$,
% die von $q$ durch Folgen von $\epsilon$-Übergängen erreichbar sind:
\[ H(q) = \{ r \in Q \mid  q \stackrel{\epsilon}{\to}_A^* r \} \]
%
Konstruktion: $B = (Q, H(S), A, T')$ mit
\[ p \stackrel{c}{\to}_B r   
\iff \exists q \in Q:  
p \stackrel{c}{\to}_A q \stackrel{\epsilon}{\to}_A^* r
\]
%
% Optimierung: in $B$ alle Zustände streichen,
% von denen in $A$ \emph{nur} $\epsilon$-Pfeile ausgehen.

\end{slide}
