614372763

Zawsze istnieje możliwość, że automat przejdzie do stanu akceptującego. Toteż, jeśli A = {Q, E, <5, go, Fj jest automatem niedeterministycznym, to:

L(A) = {w\Ś(q₀,w)eF^H)}.

Dodać należy jeszcze, że L(A) jest zbiorem słów w € E* takich, że S(qo,w) zawiera co najmniej jeden stan akceptujący.

Dowód iż automaty deterministyczny może realizować dowolny automat niedeterministyczny obejmuje tzw. konstrukcję podzbiorów. Konstrukcja podzbiorów rozpoczyna od definicja automaty niedeterministycznego N = {Qn, E, Si<i,qo, Fn}. Głównym celem jest znalezienie takiej definicji automaty deterministycznego D = {Qp, E, Sp, {go}, Fd] takiego, że L(D) = L(N). Alfabety wejściowe obydwu automatów są takie same, a stan początkowy D to zbiór zawierający jeden stan początkowy automatu N. Pozostałe elementy automatu D konstruuje się według następujących reguł:

•    Qd jest zbiorem wszystkich podzbiorów Qn (zbiorem potęgowym Q,v), ogólnie Qp może posiadać 2ⁿ stanów ale stany nieosiągalne można pominąć,

•    Fp jest zbiorem podzbiorów 5 zbioru Qn takich, że SC\Fn ^ 0, co oznacza, że Fp to zbioru stanów N zawierających co najmniej jeden stan akceptujący automatu N,

•    dla każdego zbioru S C Q_N oraz dla każdego symbolu wejściowego a G E

Sp(S,a) = (J Sn(p, a).

pes

Powyższa równość sugeruje iż aby obliczyć wartość Sp(S, a), należy przyjrzeć się wszystkim stanom p € S, dla których automat N ze stanu p przechodzi do stanu a oraz bierzemy sumę teoriomnogościową tych stanów.

Technika zamieniania niedeterministycznego automat na automat deterministyczne za pomocą podzbiór jest dość prosta. Automatu z rysunku 4 posiada zbiór złożony z trzech stanów {qo,Qi,Q2} to oznacza iż automat deterministyczny będzie zawierał co najwyżej 2³ = 8 stanów. Należy wypisać wszystkie stany oraz poprzez analizę automatu niedeterministycznego wyznaczyć przejścia do wszystkich pozostałych stanów. Poniższy rysunek prezentuje taką tabelę:

II 0 II 1

0	0	0
-{«o}	{90,9l}	{9o}
{<?i}	0	{92}
	0	0
{90,9l}	{90,91}	{90,92}
*{90,92}	{90,91}	{9o}
*{90,92}	0	{92}
*{90,91,92}	{9o,9i}	{90,92}

Choć tabela opisuje stany automatu niedeterministycznego, to fakt iż zgromadzone zostały wszystkie możliwe stany, powoduje że w istocie mamy już do czynienia z automatem deterministycznym. Wygodnie będzie zamienić poszczególne zbiory na etykiety, np.: 0 oznaczymy literą A a zbiór (go, qi} literą D. Nowa wersja tabeli funkcji przejścia po podmianie oznaczeń prezentuje się następująco:

II    o    II

A

B

D

A

F

B

D

F

^A    ||    ^A    |

—»    B    E

C    A

*    D    A

E    E

*    F    E

*    G    A

*    H    E

10