4130649334

Musimy pokazać, że relacja 8 jest funkcją i że zbiory początkowe są jednoelementowe. Drugi warunek dostajemy od razu bo zbiory początkowe automatów poprzecznych deterministycznego automatu równoległego są jednoelementowe.

Przypuśćmy teraz, że q —♦ t i q —> u są przejściami automatu IC. Wtedy g, t i u są stanami pewnego (dokładnie jednego bo przyjęliśmy rozlączność zbiorów stanów) automatu poprzecznego 8(a) automatu A. Wtedy wypisane przejścia pochodzą od pewnych przejść q —^ t i q -2-* u automatu <5(a), takich, że s€ F_a>ri i s6 F_a<r2. Ale wtedy r\ = T2 bo inaczej F_a,ri i F_a<r2 byłyby rozłączne (bo A jest deterministyczny). Tak więc ostatecznie otrzymujemy, że q —t i q u są dwoma przejściami automatu 5(a), czyli mamy t = u bo automat 8(a) jest deterministyczny.

Tym samym udowodniliśmy uwagę.    □

Stwierdzenie 2.5.4 Z każdego automatu typu sUTA można skonstruować automat typu UTA rozpoznający ten sam język tak aby rozmiar powstałego automatu był nie większy niż kwadratowy względem rozmiaru wyjściowego automatu.

Dowód:

Niech A— (Q, S, <5, {/_a}aeE> F) będzie automatem krokowym. Automat typu UTA z tezy stwierdzenia zdefiniujemy następująco:

A'= (Q,Z,8',F)

gdzie 8' (a, q) = (Q, Q, 8, I_a, {g}).

Tak więc wszystkie automaty poprzeczne są podobne do automatu poprzecznego wyjściowego automatu, a różnią się tylko stanami początkowymi i akceptującymi.

Rozmiar powstałego automatu wynosi dokładnie:

|Q| + |Q|-|E|-|QI

Więc jeżeli rozmiar alfabetu przyjmiemy za stałą to jest to rzeczywiście funkcja kwadratowa rozmiaru automatu A.    □

Uwaga 2.5.5 Jeżeli automat typu sUTA jest deterministyczny to powstały w wyniku powyższej konstrukcji automat typu UTA jest również deterministyczny.

Dowód:

Wszystkie automaty poprzeczne powstałego automatu są deterministyczne bo automat poprzeczny wyjściowego automatu krokowego jest deterministyczny i wszystkie zbiory początkowe są jednoelementowe. Rozlączność języków poprzecznych odpowiadających danej etykiecie ojca wynika z tego, że wszystkie automaty poprzeczne odpowiadające tej etykiecie mają ten sam stan początkowy i tę samą relację przejścia ale rozłączne zbiory akceptujące (dla stanu q zbiorem akceptującym jest {g}).    □

Stwierdzenie 2.5.6 Z każdego automatu typu pUTA można skonstruować automat deterministyczny (typu DpUTA) rozpoznający ten sam język. Rozmiar powstałego automatu jest najwyżej pojedynczo wykładniczo większy niż rozmiar wyjściowego automatu.