4130649326

Inaczej mówiąc (q, w, s) G S* jeżeli istnieje bieg automatu A na słowie w rozpoczynający się od stanu q i kończący się w stanie s. Zastosowaliśmy tu pojęcie biegu w nieścisły sposób ponieważ zgodnie z definicją bieg musi się rozpoczynać w stanie początkowym, ale zakładamy, że taki zabieg jest zrozumiały i będziemy go stosować również w dalszej części pracy.

Rozmiarem automatu skończonego będziemy nazywać liczbę jego stanów. Przyjmiemy oznaczenie |.A| na rozmiar automatu A.

Definicja 1.1.2 Deterministyczny automat skończony na słowach (DFA — z ang. De-terministic Finite Automaton) jest to taki automat skończony, którego relacja przejścia jest funkcją 5 : Q xE —» Q, iw którym jest tylko jeden stan początkowy. Takie automaty będziemy czasem zapisywać w postaci (Q, S, 5, qo, F) zamiast (Q, S, 5, {ęo}, F).

Ważną cechą automatu deterministycznego jest fakt, że na każdym słowie ma najwyżej jeden bieg. Automat akceptuje jeżeli ten jedyny bieg jest akceptujący. Warto zauważyć dodatkowo, że taki bieg możemy konstruować od lewej do prawej nie podejmując żadnych decyzji. Dzięki temu, że relacja przejścia jest funkcją, w żadnym miejscu nie mamy wyboru i jeżeli na pewnym słowie istnieje poprawny bieg to nie może się zdarzyć, że konstruując bieg na tym słowie napotkamy na sytuację, że nie możemy przedłużyć biegu częściowego do pełnego biegu. Uwaga ta wydaje się oczywista ale zyska ona na istotności w kontekście rozważań nad automatami działającymi na drzewach.

Przypomnimy tu jeszcze dobrze znany ale bardzo ważny fakt.

Fakt 1.1.3 (Determinizacja) Jeżeli język słów skończonych jest rozpoznawany przez pewien automat skończony to jest on również rozpoznawany przez pewien deterministyczny automat skończony.

Automat deterministyczny, o którym mowa w powyższym fakcie można skonstruować z automatu niedeterministycznego rozpoznającego dany język. Wystarczy jako stany wziąć podzbiory zbioru stanów wyjściowego automatu. Tę konstrukcję nazywamy konstrukcją podzbiorów¹. Szczegóły dowodu powyższego twierdzenia można znaleźć na przykład w książce Hopcrofta i Ullmana².

1.2. Drzewa nieurangowane

Zdefiniujemy teraz centralne pojęcie tej pracy.

Definicja 1.2.1 Drzewo nieurangowane nad skończonym alfabetem S jest to funkcja t : Dom(t) —> E, której dziedzina Dom(t) jest skończonym podzbiorem N* takim, że dla a € N tinSN* jeżeli waG Dom(t) to:

•    w ę. Dom(t) (zamkniętość na prefiksy),

•    wbE Dom(t) dla każdego b < a.

Elementy Dom(t) nazywamy węzłami (lub wierzchołkami), a wartości funkcji t — etykietami węzłów. Jeżeli aG N iwGN* to wa jest dzieckiem (lub synem) w, a w ojcem wa. Węzeł e nazywamy korzeniem, a węzły bez dzieci — liśćmi drzewa.

1

'ang. subset construction

2

zob. [HU] twierdzenie 2.1