4130649331

2.3. Automaty równoległe

Poszukamy teraz takiego modelu automatu, którego deterministyczna wersja nie będzie miała ograniczeń opisanych w poprzednim podrozdziale. Potrzebujemy więc aby bieg był nie tylko jednoznaczny ale dodatkowo, żeby można go było konstruować od liści do korzenia korzystając tylko z informacji o dotychczas wyliczonych stanach i o etykietach aktualnie rozpatrywanych węzłów, czyli bez korzystania z żadnej wiedzy przyszłej i bez zgadywania.

Odpowiednią modyfikacją automatu UTA, która może dać pożądany efekt jest automat, który równolegle symuluje działanie wszystkich automatów poprzecznych odpowiadających danej etykiecie i sprawdza, które z tych automatów zaakceptują. Równoważnie można przyjąć, że dla każdej litery a mamy jeden automat poprzeczny z osobnymi zbiorami stanów akceptujących odpowiadającymi każdemu ze stanów wierzchołkowych. Podamy teraz formalną definicję tego modelu, najpierw w wersji niedeterministycznej:

Definicja 2.3.1 Równoległy automat na drzewach nieurangowanych (pUTA — z ang. parallel Unranked Tree Automaton) to obiekt postaci A = (Q, £, 5, F), gdzie Q to skończony zbiór stanów wierzchołkowych, £ to alfabet i F C Q to zbiór stanów akceptujących. Dla każdej litery a€ £, <5(a) jest automatem skończonym na słowach nad alfabetem Q, który ma jeden zbiór akceptujący F_a>q dla każdego stanu wierzchołkowego q£ Q.

Bieg automatu A na drzewie t to takie etykietowanie A : Dom(t) —> Q, że dla każdego wierzchołka v £ Dom(t) o dzieciach vl, v2, ... ,vn istnieje bieg automatu poprzecznego 5 (t(v)) na słowie A(vl)A(u2)... A(ura) kończący się w stanie należącym do -Ft(„),A(i>) ■

Bieg akceptujący i język rozpoznawany przez automat definiujemy analogicznie jak w przypadku automatów typu UTA.

Rozmiar automatu równoległego definiujemy również podobnie jak dla poprzedniego modelu:

W = £1*001+ 101

aes

Zachodzi niemal oczywisty fakt:

Fakt 2.3.2 Język drzew nieurangowanych jest rozpoznawany przez automat typu UTA wtedy i tylko wtedy gdy jest rozpoznawany przez automat typu pUTA.

Fakt ten jest natychmiastowym wnioskiem ze stwierdzeń, które będziemy dowodzili w rozdziale 2.5.

Poniższa definicja realizuje postulaty zasygnalizowane na początku tego podrozdziału.

Definicja 2.3.3 Równoległy automat na drzewach nieurangowanych nazywamy deterministycznym (co oznaczamy przez DpUTA) jeżeli każdy z automatów poprzecznych 8(a) jest deterministyczny i dla dowolnych stanów q\, <72 £ Q i dowolnej litery a € £ zbiory F_a^_qi i F_a>g2 są rozłączne.

W takim automacie rzeczywiście bieg na drzewie t możemy konstruować od liści do korzenia bez zgadywania. Jeżeli mamy obliczone stany dla dzieci węzła v to sczytujemy je automatem S(t(v)) i patrzymy, do którego ze zbiorów Fti_v),_q należy stan, w którym skończył się bieg tego automatu poprzecznego. Węzłowi v przyporządkowujemy odpowiadający temu zbiorowi akceptującemu stan wierzchołkowy q.