Детерминированный нажимной автомат
-
Определение и свойства детерминированных нажимных автоматов
- Детерминированный нажимной автомат (DPDA) — это разновидность нажимного автомата, принимающая детерминированные контекстно-свободные языки.
- DPDA имеет не более одного допустимого перехода для каждой комбинации состояния, входного символа и символа стека.
- Формальное определение DPDA включает конечные множества состояний, входных символов, символов стека, начальное состояние, стартовый символ стека, набор принимающих состояний и функцию перехода.
-
Критерии приемлемости и распознанные языки
- Существуют два критерия приемлемости для DPDA: приемлемость по пустому стеку и приемлемость по конечному состоянию.
- Язык, принимаемый DPDA, должен быть принят для всех строк, принадлежащих языку, и быть контекстно-свободным.
- Не все контекстно-свободные языки являются детерминированными, что делает DPDA менее мощным, чем КПК.
-
Ограничения и свойства DPDA
- Ограничение DPDA одним состоянием сужает класс принимаемых языков до LL(1), что является подклассом DCFL.
- Закрытие детерминированных контекстно-свободных языков отличается от контекстно-свободных языков, например, они закрыты при дополнении, но не при объединении.
- Проблема эквивалентности для детерминированных КПК разрешима, в отличие от недетерминированных КПК.
Полный текст статьи: