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 $$\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