Оглавление
Древовидный стековый автомат
-
Определение древовидного стекового автомата
- Древовидный стековый автомат – это автомат с памятью, напоминающий потоковый автомат.
- Он распознает языки, генерируемые контекстно-свободными грамматиками.
-
Стек деревьев
- Стек деревьев – это кортеж, состоящий из дерева и указателя стека.
- Множество всех стеков деревьев обозначается TS(Γ).
-
Набор предикатов и инструкций
- Набор предикатов Pred(Γ) включает в себя предикаты для проверки истинности и равенства.
- Набор инструкций Instr(Γ) включает функции для добавления, перемещения и удаления символов из стека.
-
Древовидный стековый автомат
- Древовидный стековый автомат состоит из состояний, символов стека, входных символов, начального состояния, переходов и конечного состояния.
- Конфигурация автомата представляет собой состояние, стек и оставшееся слово для чтения.
- Переходное отношение A представляет собой бинарное отношение, объединяющее все применимые переходы.
- Язык A – это набор слов, для которых существует состояние и стек, удовлетворяющие определенным условиям.
-
Эквивалентности и ограничения
- Древовидные стековые автоматы эквивалентны машинам Тьюринга.
- Ограниченные автоматы с древовидным стеком эквивалентны автоматам pushdown, контекстно-свободным грамматикам и линейным системам контекстно-свободной перезаписи.
Полный текст статьи: