Id: eps.tex,v 1.2 2004/12/14 12:36:40 waldmann Exp
Definition. Ein -Automat ist ... mit T (Q×( {})×Q).
Definition. pAq wie früher, und pAq für (p,, q) T.
Satz. Zu jedem -Automaten A gibt es einen Automaten B mit L(A) = L(B).
Beweis: benutzt -Hüllen: H(q) = alle r Q, die von q durch Folgen von -Übergängen erreichbar sind:
Konstruktion: B = (Q, H(S), A, T') mit
Optimierung: in B alle Zustände streichen, von denen in A nur -Pfeile ausgehen.