Automat chodzący po drzewach

Automat chodzący po drzewie (TWA) to rodzaj automatu skończonego , który zajmuje się strukturami drzewiastymi , a nie łańcuchami. Koncepcja została pierwotnie zaproponowana przez Aho i Ullmana .

Poniższy artykuł dotyczy automatów chodzących po drzewach. Aby zapoznać się z innym pojęciem automatu drzewiastego, blisko spokrewnionego z regularnymi językami drzew , zobacz automat rozgałęziający .

Definicja

wszystkie drzewa są binarne , z etykietami ze stałego alfabetu Σ.

Nieformalnie automat chodzący po drzewie (TWA) A jest urządzeniem o skończonych stanach , które przechodzi po drzewie wejściowym w sposób sekwencyjny. W każdej chwili A odwiedza węzeł v w stanie q . W zależności od stanu q , etykiety węzła v oraz tego, czy węzeł jest korzeniem, lewym dzieckiem, prawym dzieckiem czy liściem, A zmienia swój stan z q na q' i przenosi się do rodzica v lub jego lewe lub prawe dziecko. TWA akceptuje drzewo, jeśli wejdzie w stan akceptacji i odrzuca, jeśli wejdzie w stan odrzucenia lub wykona nieskończoną pętlę. Podobnie jak w przypadku automatów strunowych, TWA może być deterministyczny lub niedeterministyczny.

Bardziej formalnie (niedeterministyczny) automat poruszający się po drzewie nad alfabetem Σ jest krotką A = ( Q , Σ, I , F , R , δ) gdzie Q jest skończonym zbiorem stanów, jego podzbiorami I , F i R są zbiorami odpowiednio stanów początkowych, akceptujących i odrzucających oraz δ ⊆ ( Q × { root , left , right , leaf } × Σ × { up , left , right } × Q) jest relacją przejścia.

Przykład

Prostym przykładem automatu poruszającego się po drzewie jest TWA, który wykonuje przeszukiwanie w głąb (DFS) w drzewie wejściowym. Automat ma trzy stany: $Q$$,q_{\mathit {po prawej}}\}}$${\ Displaystyle Q = \ {q_ {0}, q _ {\ mathit {lewo$ . ${\ Displaystyle A}$ zaczyna się w katalogu głównym w stanie ${\ displaystyle q_ {0}}$ i schodzi do lewego poddrzewa. Następnie przetwarza drzewo rekurencyjnie. Ilekroć wchodzi do węzła $w$ stanie $oznacza$ to, v $}$$v$ właśnie zostało przetworzone, więc przechodzi do prawego poddrzewa v $\ displaystyle v}$ . Jeśli $wejdzie$ w $stan$ _ $}}$$}$ oznacza to, że całe poddrzewo z korzeniem przetworzone i przechodzi do rodzica v $\ displaystyle$$} \ displaystyle v}$ i zmienia swój stan na ${\ displaystyle q _ {\ mathit {po lewej}}}$ lub ${\ displaystyle q _ {\ mathit {po prawej}}}$ , w zależności od tego, czy jest $dzieckiem$ .

Nieruchomości

W przeciwieństwie do automatów rozgałęziających się , automaty kroczące po drzewach są trudne do analizy: udowodnienie nawet prostych właściwości jest nietrywialne. Poniższa lista podsumowuje niektóre znane fakty związane z TWA:

• Jak wykazali Bojańczyk i Colcombet , deterministyczne TWA są zdecydowanie słabsze niż te niedeterministyczne ( ${\ Displaystyle {\ mathit {DTWA}} \ subsetneq {\ mathit {TWA}}$ )
• deterministyczne TWA są zamknięte na dopełnienie (ale nie wiadomo, czy to samo dotyczy niedeterministycznych)
• zbiór języków rozpoznawanych przez TWA jest ściśle zawarty w regularnych językach drzewa ( ${\ Displaystyle {\ mathit {TWA}} \ subsetneq {\ mathit {REG}}} )$ , tj. nie są rozpoznawane przez żaden automat chodzący po drzewach, patrz Bojańczyk i Colcombet.

Zobacz też

• Pebble automaty , rozszerzenie automatów chodzących po drzewach

Linki zewnętrzne

• Mikołaj Bojańczyk: Automaty chodzące po drzewach . Krótka ankieta.