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
p
Aq 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.