Древовидный стековый автомат

• Определение древовидного стекового автомата

  • Древовидный стековый автомат — это автомат с памятью, напоминающий потоковый автомат. 
  • Он распознает языки, генерируемые контекстно-свободными грамматиками. 

• Стек деревьев

  • Стек деревьев — это кортеж, состоящий из дерева и указателя стека. 
  • Множество всех стеков деревьев обозначается TS(Γ). 

• Набор предикатов и инструкций

  • Набор предикатов Pred(Γ) включает в себя предикаты для проверки истинности и равенства. 
  • Набор инструкций Instr(Γ) включает функции для добавления, перемещения и удаления символов из стека. 

• Древовидный стековый автомат

  • Древовидный стековый автомат состоит из состояний, символов стека, входных символов, начального состояния, переходов и конечного состояния. 
  • Конфигурация автомата представляет собой состояние, стек и оставшееся слово для чтения. 
  • Переходное отношение A представляет собой бинарное отношение, объединяющее все применимые переходы. 
  • Язык A — это набор слов, для которых существует состояние и стек, удовлетворяющие определенным условиям. 

• Эквивалентности и ограничения

  • Древовидные стековые автоматы эквивалентны машинам Тьюринга. 
  • Ограниченные автоматы с древовидным стеком эквивалентны автоматам pushdown, контекстно-свободным грамматикам и линейным системам контекстно-свободной перезаписи.