Детерминированный нажимной автомат

• Определение и свойства детерминированных нажимных автоматов

  • Детерминированный нажимной автомат (DPDA) — это разновидность нажимного автомата, принимающая детерминированные контекстно-свободные языки. 
  • DPDA имеет не более одного допустимого перехода для каждой комбинации состояния, входного символа и символа стека. 
  • Формальное определение DPDA включает конечные множества состояний, входных символов, символов стека, начальное состояние, стартовый символ стека, набор принимающих состояний и функцию перехода. 

• Критерии приемлемости и распознанные языки

  • Существуют два критерия приемлемости для DPDA: приемлемость по пустому стеку и приемлемость по конечному состоянию. 
  • Язык, принимаемый DPDA, должен быть принят для всех строк, принадлежащих языку, и быть контекстно-свободным. 
  • Не все контекстно-свободные языки являются детерминированными, что делает DPDA менее мощным, чем КПК. 

• Ограничения и свойства DPDA

  • Ограничение DPDA одним состоянием сужает класс принимаемых языков до LL(1), что является подклассом DCFL. 
  • Закрытие детерминированных контекстно-свободных языков отличается от контекстно-свободных языков, например, они закрыты при дополнении, но не при объединении. 
  • Проблема эквивалентности для детерминированных КПК разрешима, в отличие от недетерминированных КПК.