4130649330

języka S(t(v),X(v)). W szczególności liść o etykiecie a może mieć przypisany tylko taki stan q, dla którego £€ó(a,q).

Bieg A automatu jest akceptujący jeżeli A(s) G F. Automat A akceptuje drzewo t jeżeli istnieje bieg akceptujący automatu A na drzewie t. Przez L(A) będziemy oznaczać język wszystkich drzew akceptowanych przez automat A. Mówimy, że automat A rozpoznaje język L jeżeli L = L(A).

Jeżeli chcemy mówić o rozmiarze automatu typu UTA to musimy określić jak będziemy reprezentować języki poprzeczne, czyli języki 6(a,q). Dokonamy najbardziej naturalnego w tej sytuacji wyboru i założymy, że dla każdego a G S i q G Q mamy niedeterministyczny automat skończony działający na słowach nad Q rozpoznający język S(a,q). Automaty te będziemy nazywać automatami poprzecznymi, a ich stany stanami poprzecznymi (dla odróżnienia od stanów wierzchołkowych).

Dzięki temu możemy założyć, że 5 jest po prostu funkcją, której wartościami są automaty skończone nad Q. W tej pracy, będziemy zamiennie używać 5(a,q) na oznaczenie odpowiedniego języka poprzecznego i na oznaczenie odpowiedniego automatu poprzecznego.

Rozmiarem |.A| automatu A będziemy nazywać sumę liczby stanów automatów poprzecznych i liczby stanów automatu A.

2.2. Deterministyczne automaty typu UTA

O biegu A automatu A — (Q, E, 5, F) typu UTA na drzewie t należy myśleć w następujący sposób. Najpierw wybierane są (niedeterministycznie) stany dla liści drzewa. Potem dla każdego węzła v, którego dzieci mają wyliczone stany wybieramy q£ Q i sczytujemy automatem S(t(v),q) słowo złożone ze stanów przyporządkowanych kolejnym dzieciom węzła v. Jeżeli automat ten zaakceptuje słowo, to węzłowi v możemy przyporządkować stan q.

Widać, że w takich automatach niedeterminizm przejawia się na dwa sposoby. Po pierwsze dla każdego węzła niedeterministycznie dokonywany jest wybór automatu poprzecznego, którym sczytywane są stany przypisane jego dzieciom, a po drugie niedeterministyczne mogą być same automaty poprzeczne. Oba te aspekty zostały wzięte pod uwagę w poniższej definicji.

Definicja 2.2.1 Automat na drzewach nieurangowanych będziemy nazywać deterministycznym (i oznaczać DUTA) jeżeli wszystkie automaty poprzeczne są deterministyczne i dla każdej litery aG E i dla dowolnych stanów qi,q2 € Q języki S(a,qi) i S(a,<72) są rozłączne.

Trzeba jednak zauważyć, że determinizm automatów DUT A jest w pewien sposób ograniczony. Powyższa definicja zapewnia, że na każdym drzewie taki automat ma nie więcej niż jeden bieg, bo każdy węzeł może mieć przypisany najwyżej jeden stan wierzchołkowy. Jeżeli jednak przyjrzymy się w jaki sposób ten bieg jest konstruowany to zauważymy, że wyliczając stan dla każdego węzła automat musi najpierw zgadnąć jakiego automatu poprzecznego użyć, żeby tamten zaakceptował. Taka sytuacja odpowiada bardziej koncepcji automatu jednoznacznego (ang. unambiguous) niż deterministycznego.

Powyższe spostrzeżenie jest jednym z powodów, dla których w literaturze rozważa się też inne modele automatów działających na drzewach nieurangowanych¹. Niektóre z tych modeli omówimy w kolejnych podrozdziałach.

1

Inne powody omówione są w [MN]. Zaliczają się do nich między innymi niejednoznaczność i nieefektywność minimalizacji automatów typu DUT A.