Automaten mit Epsilon-Übergängen

Id: eps.tex,v 1.1 2007-10-31 17:50:50 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) = {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



Johannes Waldmann 2008-01-24