4130649332

2.4. Automaty krokowe

Możemy pójść jeszcze o krok dalej w upraszczaniu konstrukcji biegu automatu. Automat równoległy ma osobne automaty poprzeczne dla każdej litery z alfabetu, natomiast ostatnia klasa automatów jaką będziemy rozważać w tej pracy ma tylko jeden automat poprzeczny. Albo raczej, automaty poprzeczne różnią się tylko zbiorami stanów początkowych i akceptujących, bo dla każdej etykiety ojca rozpatrywanego ciągu dzieci automat poprzeczny ma osobny zbiór stanów początkowych.

W tym modelu dokonamy jeszcze jednej modyfikacji — automat będzie miał tylko jeden zbiór stanów. Automat poprzeczny będzie wykorzystywał zbiór stanów wierzchołkowych. Stan wyliczony po sczytaniu wszystkich dzieci węzła u będzie przypisywany węzłowi u.

Definicja 2.4.1 Automat krokowy na drzewach nieurangowanych (sUTA — z ang. stepwise Unranked Tree Automaton) to obiekt postaci A — {Q, £, 8, {I_a}aeT., F), gdzie Q to skończony zbiór stanów, £ to alfabet, I_a Q Q to zbiory stanów początkowych, F — zbiór stanów akceptujących, a8QQxQxQ to relacja przejścia automatu poprzecznego. Automat poprzeczny ma więc alfabet taki sam jak zbiór stanów.

Bieg automatu A na drzewie t to takie etykietowanie A : Dom(t) —» Q, które dla każdego węzła v € Dom(t) o dzieciach ul, u2, ..., vn spełnia warunek: istnieje bieg akceptujący automatu skończonego (Q, Q, S, Ią_v)> (A(u)}^ ^na słowie A(ul)A(u2)... A(un).

Bieg akceptujący i język rozpoznawany przez automat A są zdefiniowane analogicznie jak dla poprzednich modeli.

Na automat A — (Q, £, 5, {/_a}a€E> F) typu sUTA możemy więc patrzeć jak na automat typu pUTA, w którym automat poprzeczny odpowiadający etykiecie a używa relacji przejścia 8, ma zbiór stanów początkowych równy I_a a zbiór akceptujący odpowiadający stanowi wierzchołkowemu q równy {ę}.

Za rozmiar automatu krokowego będziemy oczywiście uważali liczbę jego stanów.

Sformułujemy tu analogiczny jak dla modelu pUTA fakt, który również będzie natychmiastowym wnioskiem ze stwierdzeń, które udowodnimy w rozdziale 2.5.

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

Definicja 2.4.3 Automat krokowy na drzewach nieurangowanych A = {Q, £, (5, {/_a}a€£ł F) nazwiemy deterministycznym (DsUTA) jeżeli wszystkie automaty skończone postaci (Q,Q,S,I_a,{q}) są deterministyczne. Taki automat będziemy czasem zapisywać A-{Q, £, 5, {<7a}ae£, F) zamiast A = (Q, £, <5, {{9a}}aes, F).

2.5. Porównanie rozmiarów różnych rodzajów automatów

W tym rozdziale porównamy rozmiary wyżej opisanych automatowych reprezentacji regularnych języków drzew nieurangowanych. Pokażemy w szczególności, że istnieją konwersje pomiędzy wszystkimi trzema typami automatów niedeterministycznych nie zmieniające rozmiaru bardziej niż wielomianowo. Wnioskiem z rozważań przedstawionych w tym rozdziale będzie między innymi fakt, że wszystkie wyżej opisane modele (również deterministyczne!) mają taką samą siłę wyrazu.

Stwierdzenie 2.5.1 Dla dowolnego automatu typu UTA istnieje automat typu pUTA tego samego rozmiaru rozpoznający ten sam język.