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

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