614372764

Jeśli prześledzi się dokładnie pracę automatu począwszy od stanu B, okaże się iż i ośmiu wszystkich możliwych stanów, osiągalne są tylko trzy B, E oraz F. Pozostałe pięć stanów są nieosiągalne i mogą zostać pominięte. Ta technika budowy stanu deterministycznego, wymaga jednak wykładniczej ilości kroków w budowie pierwszej wersji tabeli funkcji przejścia.

Można spróbować wyeliminować taki sposób budowy, poprzez „leniwe” obliczanie za pomocą funkcji przejścia oraz wykorzystać indukcję. Niech N będzie automatem niedeterministycznym przedstawionym na rysunku 4. Podstawa: Jednoelementowy zbiór złożony tylko ze stanu początkowego automatu N jest osiągalny.

Krok Indukcyjny: Zakładając że zbiór S stanów jest osiągalny, należy obliczyć dla każdego symbolu a zbiór stanów za pomocą funkcji przejścia Sd{S, a). Naturalnie otrzymane stany także będą osiągalne.

Ponieważ {go} jest już stanem automatu deterministycznego D (krok podstawowy), to obliczając wartość funkcji przejścia odpowiednio otrzymamy, (5d({9o},0) = {go, c/i} oraz <Sd({9o}, 1) = {go}- Wartości te znajdują także w tabeli funkcji przejścia przedstawionej wcześniej, ale można, a nawet należy, je odczytać z diagramu automatu N - rysunek 4.

Stan {go} to już analizowany przez nas, nowym stanem jaki otrzymaliśmy jest {go, 9i }• Obliczając jego przejścia odpowiednio otrzymamy: Jd({9o, gi}, 0) = {go,gi} oraz <5d({<2o, 9i}> 1) = {go, 92} dokładniej obliczenia przyjmują następującą postać:

<M{go,gi},0) = <Mg_o,0)U <M«i,0) = {go,gi}u0 = {go,gi},

■5d({<7o,9i}, 1) = ńjv(go, 1) U <Sjv(9i> 1) = {90} U {92} = {90,92}-Nowym stanem jest {90,92}, z obliczeń wartości funkcji przejścia otrzymamy:

<M{9o,92},0) =<M9o,0)U<5at(92,0) = {9o,9i}U0 = {90,91},

<M{9o, 92}, 1) = <M9o, !) ^u <M92,1) = {9o} U 0 = {90}.

Ponieważ nie otrzymaliśmy nowych stanów, to procedura się kończy i otrzymaliśmy deterministyczny opis automatu N. Rysunek 8 przedstawia diagram tego nowego automatu. □

Rysunek 8: Deterministyczny automat skończony akceptujący wyrazy kończące się wyrażeniem 01 zbudowany z automatu niedeterministycznego z Rysunku 4

Przykład z konwersją automatu niedeterministycznego za pomocą techniki podzbiorów pokazuje iż każdy automat niedeterministyczny ma odpowiedni automat deterministyczny choć liczba stanów może ulec zmianie jednak nie będzie większa niż 2" (n - liczba stanów automatu niedeterministycznego). Oznacza to iż języki akceptowany przez obudwa automaty są takie same. Mówi o tym także następujące twierdzenie.

Twierdzenie 1 Jeśli D = {Qd, E, $d, {90},^} jest deterministycznym automatem zbudowanym z niedeterministycznego automatu N = {Qn, E,<5w, 9o> Fn} za pomocą konstrukcji podzbiorów, to L(D) = L(N).

Dowód:

Należy dzięki indukcji pokazać, że słowo w:

^d({9o,m’}) = <Śn({9o,w})

Należy zwrócić uwagę na to iż co prawda obydwie funkcje 6 zwracają zbiór stanów z Qn, przy czym Sd interpretuje ten zbiór jako jeden ze stanów Qd (będącego zbiorem potęgowym Qn), natomiast Sn interpretuje ten sam zbiór jako podzbiór Qn-

11