Введение
В теории автоматов, детерминированный автомат с магазинной памятью (DPDA или DPA) является разновидностью автомата с магазинной памятью. Класс детерминированных автоматов с магазинной памятью распознает детерминированные контекстно-свободные языки, являющиеся собственным подмножеством контекстно-свободных языков. Переходы автомата определяются текущим состоянием, входным символом и текущим верхним символом в стеке. Символы, находящиеся ниже в стеке, не видны и не оказывают непосредственного влияния. Действия автомата включают добавление, удаление или замену символа на вершине стека. Детерминированный автомат с магазинной памятью имеет не более одного допустимого перехода для данной комбинации входного символа, состояния и верхнего символа стека. В этом его отличие от недетерминированного автомата с магазинной памятью.
Признанные языки
Если язык принимается конечным автоматом с магазинной памятью (PDA), то он также может быть принят детерминированным конечным автоматом с магазинной памятью (DPDA) тогда и только тогда, когда для всех строк, принадлежащих этому языку, существует единственное вычисление от начальной конфигурации до принимающей. Если язык может быть принят PDA, то это контекстно-свободный язык, а если он может быть принят DPDA, то это детерминированный контекстно-свободный язык (DCFL). Не все контекстно-свободные языки являются детерминированными. Это делает DPDA строго более слабым устройством, чем PDA. Например, язык Lp, состоящий из палиндромов четной длины в алфавите 0 и 1, имеет контекстно-свободную грамматику S → 0S0 | 1S1 | ε. Если для этого языка существует DPDA, и он считывает строку 0n, то он должен использовать свой стек для запоминания длины n, чтобы иметь возможность различать возможные продолжения 0n110n ∈ Lp и 0n110n+2 ∉ Lp. Следовательно, после прочтения 0n110n, сравнение длины после "11" с длиной до "11" снова опустошит стек. По этой причине строки 0n110n0n110n ∈ Lp и 0n110n0n+2110n+2 ∉ Lp не могут быть различимы. Ограничение DPDA одним состоянием уменьшает класс принимаемых языков до языков LL(1), которые являются собственным подклассом DCFL. В случае с PDA это ограничение не оказывает влияния на класс принимаемых языков.
Закрытие
Свойства закрытия детерминированных контекстно-свободных языков (принятых детерминированным автоматом с магазинной памятью по конечному состоянию) резко отличаются от свойств закрытия контекстно-свободных языков. Например, они (эффективно) замкнуты относительно дополнения, но не замкнуты относительно объединения. Доказать, что дополнение языка, распознаваемого детерминированным автоматом с магазинной памятью, также распознается детерминированным автоматом с магазинной памятью, — непростая задача. По сути, необходимо избегать бесконечных вычислений. Как следствие из замкнутости относительно дополнения, можно решить, принимает ли детерминированный автомат с магазинной памятью все слова над своим входным алфавитом, проверив дополнение этого языка на пустоту. Это невозможно для контекстно-свободных грамматик (и, следовательно, для не детерминированных автоматов с магазинной памятью).
Проблема эквивалентности
Герауд Сеньезерг (1997) доказал, что проблема эквивалентности для детерминированных PDA (то есть, для двух детерминированных PDA A и B, совпадает ли L(A) с L(B)?) является разрешимой, за что он получил премию Гёделя в 2002 году. Для недетерминированных PDA проблема эквивалентности неразрешима.