Automaten mit Epsilon-Übergängen

Id: eps.tex,v 1.3 2005/10/19 22:19:55 waldmann Exp

Def. Ein $\epsilon$-Automat ... 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 (ohne $\epsilon$-Kanten) 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 | q$$\;\stackrel{{\epsilon}}{{\to}}\;$$_A^*r}

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

p$$\;\stackrel{{c}}{{\to}}\;$$_Br$$\iff$$$$\exists$$q $$\in$$ Q : p$$\;\stackrel{{c}}{{\to}}\;$$_Aq$$\;\stackrel{{\epsilon}}{{\to}}\;$$_A^*r