Automaten mit Epsilon-Übergängen

Id: eps.tex,v 1.2 2004/12/14 12:36:40 waldmann Exp

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

Definition. p$ \;\stackrel{c}{\to}\;$Aq wie früher, und p$ \;\stackrel{\epsilon}{\to}\;$Aq 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 $\displaystyle \in$ Q | q$\displaystyle \;\stackrel{\epsilon}{\to}\;$A*r}

Konstruktion: B = (Q, H(S), A, T') mit

p$\displaystyle \;\stackrel{c}{\to}\;$Br$\displaystyle \iff$$\displaystyle \exists$q $\displaystyle \in$ Q : p$\displaystyle \;\stackrel{c}{\to}\;$Aq$\displaystyle \;\stackrel{\epsilon}{\to}\;$A*r

Optimierung: in B alle Zustände streichen, von denen in A nur $ \epsilon$-Pfeile ausgehen.



Johannes Waldmann 2005-01-28