4130649333

Dowód:

Niech A = (Q, £, 5, F) będzie automatem typu UTA. Szukany automat równoległy ma ten sam zbiór stanów wierzchołkowych i zbiór stanów akceptujących co automat A.

Jedyna zmiana dotyczy automatów poprzecznych. W automacie A mieliśmy osobne automaty poprzeczne dla każdej litery i dla każdego stanu wierzchołkowego. W nowym automacie będzie tylko jeden automat poprzeczny dla każdej litery. Możemy go skonstruować biorąc sumę rozłączną wszystkich automatów poprzecznych wyjściowego automatu odpowiadających tej literze.

Zbiory stanów akceptujących automatów poprzecznych są natomiast bezpośrednio odziedziczone z automatu wyjściowego. Możemy tak zrobić bo zgodnie z definicją automatu równoległego każdy automat poprzeczny ma właśnie osobny zbiór akceptujący dla każdego stanu wierzchołkowego.    □

Stwierdzenie 2.5.2 Dla dowolnego automatu typu pUTA istnieje automat typu sUTA nie większego rozmiaru rozpoznający ten sam język.

Dowód:

Niech A = (Q, E, <5, F) będzie automatem typu pUTA i niech automaty poprzeczne tego automatu wyglądają następująco:

«(«) = «.. <3, k.MfirfW

gdzie F_atq to zbiór akceptujący odpowiadający stanowi wierzchołkowemu q.

Skonstruujemy automat krokowy IC rozpoznający ten sam język.

Bez straty ogólności możemy założyć, że automaty poprzeczne automatu A mają parami rozłączne zbiory stanów. Za zbiór stanów automatu krokowego (wykorzystywany również przez automat poprzeczny) weźmiemy sumę zbiorów stanów wszystkich automatów poprzecznych automatu A. Automat poprzeczny używa tego zbioru stanów jako alfabetu, natomiast w automacie A alfabetem dla automatu poprzecznego był zbiór Q stanów wierzchołkowych. Automat poprzeczny automatu krokowego chcąc symulować automaty poprzeczne automatu A będzie musiał przeliczać sobie jaki stan wierzchołkowy automatu A mógłby się pojawić w miejscu gdzie stoi stan poprzeczny tego automatu.

Tak więc relacja przejścia automatu IC będzie wyglądała następująco: jeżeli q —> p jest przejściem pewnego automatu poprzecznego ó(a) automatu A, to q —» p jest przejściem automatu IC dla każdego s € F_a,_r-

Zbiory początkowe automatu krokowego są takie same jak zbiory początkowe automatów poprzecznych automatu A. Natomiast zbiór akceptujący składa się z tych stanów, które w automacie A mogłyby być przepisane na któryś stan akceptujący, a więc jest to zbiór:

U flw

a€S,g€F

□

Uwaga 2.5.3 Jeżeli automat A typu pUTA jest deterministyczny to powyższa konstrukcja daje automat sUTA, który również jest deterministyczny.

Dowód: