614372765

Podstawa: Niech |w| = 0, tzn. w = s. Na podstawie definicji 5 dla determistycznych i niedeterministycznych automatów wiemy iż <5d({<Zo},£) = ^/v({<7o},£) = {<7o}-

Krok indukcyjny: Niech |?c| = n + 1 oraz niech stwierdzenie będzie prawdziwe dla wejść o długości n. Jeśli w = xa, gdzie a jest ostatnim symbolem w, to na mocy założenia indukcyjnego Ód({9o}- *) = <5w({<jo}, #)• Niech oba te zbiory stanów N mają postać {pi,p2i • • • ,Pfc}-

Definicja S dla automatu niedeterministycznego pokazuje iż

k

<Św(?o, w) = IJ Śn/{pi,a).

t=i

Natomiast konstrukcja podzbiorów pokazuje

Korzystając z konstrukcji podzbiorów oraz z faktu, że <5d({<?o}, ^x) — {P11P2, • ■ ■,p*}w części indukcyjnej definicji S dla automatów deterministycznych:

<M{ąo}, z) = <M<M{ąo},x), a) = <5d({pi,P2, • • ■ ,Pt}, o) = U S_N(pi,a).

i=i

W ten sposób dowiedliśmy, że <5d({<70) wi}) = Óat({(J0iUi}). Automaty D oraz N akceptują słowo w wtedy i tylko wtedy, gdy odpowiednio Jd({9o}iw0 i <$w({9o}iW) zawierają stan z Fn. □

Następne twierdzenie uogólnia przedstawione powyżej twierdzenie:

Twierdzenie 2 Niech L będzie zbiorem akceptowanym przez niedeterministyczny automat skończony. Wtedy istnieje deterministyczny automat skończony akceptujący L.

Szkic dowodu:

Ponieważ w twierdzeniu zostało użyte wyrażenie „wtedy i tylko wtedy”, oznacza to iż należy dowód podzielić na dwie implikacje. Pierwsza implikacja <= oznacza iż automat niedeterministyczny jest zamieniany na automat deterministyczny. A jest to nic innego, jak konstrukcja podzbiorów i twierdzenie które zostało omówione powyżej.

Można wobec tego przejść do drugiej części dowodu, implikacji =S-. Należy zamienić automat deterministyczny na identyczny automat niedeterministyczny. Co sprowadza się do intuicyjnego interpretowania diagramu przejść automatu deterministycznego jako automatu niedeterministycznego. Automat niedeterministyczny będzie posiadał tylko i wyłącznie jedno przejście. Formalnie, należy pokazać na poziomie funkcji przejścia, że dla deterministycznego automatu D = {Qd, 2, Sd. %• Fd} określamy równoważny automat niedeterministyczny N = {Qn, £, ó,v, <?0i Ffj}, w którym funkcja przejścia Sn jest określona przez regułę:

Sd (g, a) = P => S_N (q, a) - {p}

Względnie łatwo pokazać dzięki indukcji, długości słowa w, iż jeśli So(qo,a) = p, to

= {p}-

Takie podejście oznacza iż w jest akceptowane przez D wtedy i tylko wtedy, gdy jest ono akceptowany przez automat N, co oznacza L(D) = L(N). □

2.2 Konwersja automatu z przejściami e na automat deterministyczny

Sposób eliminacji przejść e oraz konwersja automaty niedeterministycznego na deterministyczny jest podobny do konstrukcji podzbiorów ale wykorzystywane jest także e-domknięcie. Równoważny automat deterministyczny D = {Qq,T,,Sd, </0i F_d) jest budowany w oparciu o automat E = {Qe, ^,<5e,?0i Fe) w następujący sposób:

1.    Qd jest zbiorem podzbiorów Qe- Wszystkie osiągalne stany D są e-domkniętymi podzbiorami Qe, tj. zbiorami S C Q_E takimi, że 5 = ED(S).

2.    qo = ED(<jo), stan początkowy D otrzymujemy, poprzez domknięcie zbioru złożonego jedynie ze stanu początkowego E.

12