Automaton podróżujący

PLC podróży drzew , zwany w skrócie PLC podróżując (angielski drzewo walking automatem (TWA)) jest wariantem automatów skończonych , która działa na drzewach zamiast słów . Koncepcja została już zdefiniowana przez Aho i Ullmana w 1971 roku.

Ten artykuł dotyczy automatów podróżujących. Automaty drzewo (rosnąco lub malejąco) to inna klasa automatów i rozpoznać języków regularnych drzewa .

Nieformalny opis

Te drzewa uważane są tu traktowane jako binarne i oznaczone symbolami stałej alfabetu Ď.

Automat posuwowy A jest automatem skończonym, który przechodzi przez drzewo sekwencyjnie. Rozpoczyna się u nasady i kończy u nasady. W danym momencie automat A „odwiedza” węzeł v i jest w określonym stanie. W zależności od stanu, etykiety węzła v i typu węzła (czy jest to korzeń, lewe czy prawe dziecko, czy może liść?), Automat A zmienia stan i przechodzi do rodzica v lub do jednego z jego dzieci. Automat akceptuje dane drzewo, jeśli kończy się ono w końcowym stanie u korzenia. Jeśli chodzi o automaty słowne, automaty podróżujące mogą, ale nie muszą być deterministyczne.

Definicja

Automat podróżujący (niedeterministyczny) A = ( Q , Σ, I , F , R , δ) składa się z następujących danych:

Q jest skończonym zbiorem stanów,
Σ to alfabet,
I , F i R to podzbiory stanów, odpowiednio stany początkowe, akceptacji i odrzucenia
T jest zbiorem dostępnych „typów”: { węzeł wewnętrzny , liść } × { root , left child , child right }
δ ⊆ Q × T × Σ × { góra , lewo , prawo } × Q jest relacją przejścia.

Relacja przejścia działa zatem w zależności od stanu, typu węzła, a także symbolu odczytywanego na węźle, decyduje o ruchu i zmienia stan.

PLC konfiguracja jest para utworzona ( Q , V ) o stanie i węzła. Sterownik uruchamia się w konfiguracji początkowej składającej się ze stanu początkowego i katalogu głównego. Kończy się, jeśli akceptuje drzewo, w konfiguracji terminala utworzonej przez stan terminala i root.

Przykład

Oto przykład automatu trawersowego, który wykonuje algorytm przejścia w głąb (DFS) na danym drzewie. Regulator ma 3 stany, . Automat zaczyna od korzenia stanu i przechodzi do lewego poddrzewa. Następnie kontynuuje rekurencyjnie: wchodząc do węzła będąc w stanie , oznacza to, że właśnie przetworzył lewe poddrzewo i przechodzi do przetwarzania prawego poddrzewa . Jeśli wejdzie do węzła w stanie , oznacza to, że całe poddrzewo główne zostało odwiedzone i przechodzi do rodzica, zmieniając jego stan na lub , w zależności od tego, czy jest to lewe, czy prawe dziecko. $W$ ${\ displaystyle Q = \ {q_ {0}, q _ {\ ell}, q_ {r} \}}$ ${\ displaystyle q_ {0}}$ $W$ $v$ ${\ displaystyle q _ {\ ell}}$ $v$ $v$ $W$ $v$ $q_ {r}$ $v$ $W$ $v$ ${\ displaystyle q _ {\ ell}}$ $q_ {r}$ $v$

Oto inne przykłady: Możemy pokazać, że zbiór drzew, których wszystkie liście mają ten sam stały symbol a, jest rozpoznawalny przez podróżujący automat. Mówiąc bardziej ogólnie, zbiór drzew, których liście niosą słowo ustalonego, regularnego języka, jest rozpoznawalny przez kroczący automat.

Nieruchomości

Niektóre podstawowe właściwości są łatwe:

Języki drzew rozpoznawane przez automaty podróżujące są zamykane przez zjednoczenie i przecięcie.
Język drzewa rozpoznawany przez automat przemierzający jest również rozpoznawany przez automat drzewa (ale włączenie jest ścisłe, patrz poniżej).

W przeciwieństwie do automatów drzewiastych, automaty podróżujące są trudne do analizy. Oto kilka właściwości, które trudno udowodnić:

Deterministyczne automaty trawersowe są mniej wydajne niż niedeterministyczne automaty trawersowe.
Języki drzew rozpoznawane przez deterministyczne automaty ścieżkowe są zamykane przez komplementację (w przypadku automatów niedeterministycznych problem jest otwarty).
Wszystkie języki rozpoznawane przez automaty podróżujące są ściśle zawarte w rodzinie języków rozpoznawanych przez automaty drzewiaste.
Sprawdź, czy język rozpoznawany przez automaty podróżne jest pusty, jest WYJĄTKOWY-kompletny .

Załączniki

Powiązany artykuł

Automat żetonowy , rozszerzenie automatów podróżujących.

Bibliografia

Alfred V. Aho i Jeffrey D. Ullman , „ Tłumaczenia w gramatyce bezkontekstowej ”, Information and Control , vol. 19 N O 5,1971, s. 439–475 ( DOI 10.1016 / S0019-9958 (71) 90706-6 , czytaj online )
Mikołaj Bojańczyk i Thomas Colcombet, „ Nie można określić automatów chodzących po drzewach ”, Informatyka teoretyczna , t. 350 n kości 2-3,2006, s. 164-173 ( DOI 10.1016 / j.tcs.2005.10.031 , czytaj online )
Mikołaj Bojańczyk i Thomas Colcombet, „ Automaty do chodzenia po drzewach nie rozpoznają wszystkich języków regularnych ”, SIAM Journal on Computing , t. 38 N O 22008, s. 658–701 ( DOI 10.1137 / 050645427 , czytaj online )
Mikołaj Bojańczyk, „Automaty do chodzenia po drzewach” , w: C. Martin-Vide, F. Otto i H. Fernau (red.), Language and Automata Theory and Applications, LATA 2008, Tarragona , Springer,2008( ISBN 9783540882817 ) , str. 1-2.
Anca Muscholl, Mathias Samuelides i Luc Segoufin, „ Complementing deterministic tree-walking Automata ”, Information Processing Letters , vol. 99, n o 1,2006, s. 33-39.

Link zewnętrzny

Mikołaj Bojańczyk, „ Automaty do chodzenia po drzewach ” .