Rekurencyjna sieć przejść

Rekurencyjna sieć przejść (ang. recursive transition network, RTN) zwana czasem basic transition network (BTN) jest matematycznym modelem automatu do generowania/akceptowania słów gramatyki przedstawionym w postaci grupy skierowanych grafów.

Na RTN składają się stany oraz łuki. Jest jeden stan początkowy i zbiór stanów końcowych. Łuki mogą być oznakowane symbolami terminalnymi, podobnie jak to jest w automacie skończonym, ale również symbolami nieterminalnymi z dodatkowymi akcjami PUSH I POP.

Napotykając łuk z taką etykietą, zamiast przechodzić do następnego stanu, przechodzimy do początkowego stanu (operacja PUSH) innego lub tego samego grafu, gdzie kontynuujemy wędrówkę aż do któregoś ze stanów końcowych, gdzie wracamy (operacja POP) do grafu, w którym byliśmy poprzednio idąc do stanu, który wskazuje ten łuk.

Łuki mogą mieć być któregoś z typu:

WRD - symbol terminalny

CAT - przechodzimy, gdy symbol należy do pewnej kategorii (często używane w przetwarzaniu gramatyk języka naturalnego)

JMP - przejście bez pobierania żadnego symbolu z wejścia, działa tak samo jak ε-przejścia automatu niedeterministycznego

PUSH - zapamiętane jest bieżące położenie (który graf i który stan) oraz przejście na początek odpowiedniego grafu.

POP - to raczej nie typ łuku ale działanie, które następuje w stanach końcowych - przejście do miejsca, które zostało ostatnio odłożone na stos.

Sieć RTN może sprawdzać gramatykę bezkontekstową, w odróżnieniu od automatów skończonych bez stosu ograniczonych do wyrażeń regularnych.

Rozważmy gramatykę palindromiczną $a^{k}b^{n}c^{k},k,n>0$ generowaną przez produkcje:

• $S\rightarrow aSc$
• $S\rightarrow aPc$
• $P\rightarrow Pb$
• $P\rightarrow b$

Sieć RTN będzie wyglądała: