4130649335

Dowód:

Zastosujemy konstrukcję podobną do konstrukcji podzbiorów stosowanej przy determini-zacji automatów skończonych.

Niech A=(Q,T,,S, F) będzie automatem równoległym i niech jego automaty poprzeczne wyglądają następująco:

«(<>)■ = (0..<3,«X, U, {F«, ,},«3)

Stanami wierzchołkowymi automatu deterministycznego będą podzbiory zbioru stanów wierzchołkowych automatu A. Każdy automat poprzeczny determinizujemy stosując standardową konstrukcję podzbiorów, więc: za stany bierzemy podzbiory stanów, wtedy stan początkowy to zbiór stanów początkowych, a relacja (a właściwie funkcja) przejścia wylicza wszystkie stany, które mogą być osiągnięte ze stanów z aktualnego zbioru.

Formalnie: dla P C Q_a i R C Q w odpowiednim automacie poprzecznym automatu deterministycznego mamy następujące przejście:

P {« e <3. : 3refl3p<EP (p. r, q) 6 5„}

bo, jak pamiętamy, dla automatu poprzecznego symbolami alfabetu są stany wierzchołkowe.

Musimy teraz określić zbiory akceptujące automatów poprzecznych. I tak, zbiór akceptujący odpowiadający literze a G E i stanowi wierzchołkowemu R C Q zawiera te stany-podzbiory, które mogą powodować przypisanie ojcu dokładnie wszystkich stanów z R. Czyli formalnie jest to zbiór:

[P QQa - V<jefi3_pGp p£F_a,_q A V_9€Q\p-i3_pGppeF_a,₉|

Do zbioru akceptującego całego równoległego automatu deterministycznego należą te podzbiory Q, które mają niepuste przecięcie ze zbiorem akceptującym F wyjściowego automatu.

Rozmiar tak skonstruowanego automatu deterministycznego jest nie większy niż 2^1. □

Warto zauważyć, że powyższe powiększenie podczas determinizacji może być konieczne, to znaczy:

Uwaga 2.5.7 Istnieje ciąg języków drzew nieurangowanych {Xn}neN taki, że każdy język L_n jest rozpoznawany przez pewien automat typu pUTA rozmiaru wielomianowego względem n, ale każdy automat typu DpUTA rozpoznający L_n ma rozmiar co najmniej wykładniczy względem n.

Dowód:

Żeby uzasadnić tę uwagę skorzystamy z tego, że podobny fakt jest prawdziwy dla deterministycznych i niedeterministycznych automatów skończonych na słowach.

Rozważmy na przykład klasę {M_n}_nepj języków słów nad alfabetem {0,1} taką, że M_n to język słów, w których n-tą od końca literą jest 1. Wtedy język M_n jest rozpoznawany przez automat niedeterministyczny on+1 stanach: automat zgaduje n-tą od końca pozycję, sprawdza czy stoi na niej 1 i potem tylko sprawdza czy rzeczywiście do końca jest n — 1 pozycji. Natomiast automat deterministyczny musi cały czas pamiętać ostatnich n znaków — można udowodnić, że słowa o różnych sufiksach n-literowych są w innych klasach abstrakcji relacji syntaktycznej.

Za L_n weźmiemy teraz język takich drzew nieurangowanych wysokości 2, w których dzieci korzenia tworzą słowo należące do M_n.

Oczywiście tak określona klasa spełnia warunki opisane w powyższej uwadze.    □

Poniższe twierdzenie podsumowuje wszystkie fakty udowodnione w tym rozdziale.