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

В теории автоматов детерминированный автомат с выталкиванием ( DPDA или DPA ) является разновидностью автомата с выталкиванием . Класс детерминированных автоматов с выталкиванием вниз принимает детерминированные контекстно-свободные языки , собственное подмножество контекстно-свободных языков .

Машинные переходы основаны на текущем состоянии и входном символе, а также на текущем верхнем символе стека. Символы ниже в стеке не видны и не имеют немедленного эффекта. Действия машины включают толкание, выталкивание или замену вершины стопки. Детерминированный автомат с понижающей передачей имеет не более одного допустимого перехода для одной и той же комбинации входного символа, состояния и символа верхнего стека. В этом его отличие от недетерминированного автомата с выталкиванием.

Формальное определение

(не обязательно детерминированный) КПК $M$ можно определить как семикортеж:

$M=(Q\,,\Sigma \,,\Gamma \,,q_{0}\,,Z_{0}\,,A\,,\delta \,)$

где

• $Q\,$ это конечное множество состояний
• $\Sigma \,$ представляет собой конечный набор входных символов
• $\Gamma \,$ это конечный набор символов стека
• $q_{0}\,\in Q\,$ это начальное состояние
• $Z_{0}\,\in \Gamma \,$ это начальный символ стека
• $A\,\subseteq Q\,$, где $A$ это набор принимающих или окончательных состояний
• $\delta \,$ является функцией перехода, где

$\delta \colon (Q\,\times (\Sigma \,\cup \left\{\varepsilon \,\right\})\times \Gamma \,)\longrightarrow {\mathcal {P}}(Q\times \Gamma ^{*})$

где $*$ это звезда Клини , что означает, что $\Gamma ^{*}$ — это «набор всех конечных строк (включая пустую строку $\varepsilon$) элементов $\Gamma$", $\varepsilon$ обозначает пустую строку и ${\mathcal {P}}(X)$ это набор мощности набора $X$.

M является детерминированным , если он удовлетворяет обоим следующим условиям:

• Для любого $q\in Q,a\in \Sigma \cup \left\{\varepsilon \right\},x\in \Gamma$, набор $\delta (q,a,x)\,$ имеет не более одного элемента.
• Для любого $q\in Q,x\in \Gamma$, если $\delta (q,\varepsilon ,x)\not =\emptyset \,$, затем $\delta \left(q,a,x\right)=\emptyset$ для каждого $a\in \Sigma .$

Существует два возможных критерия приемки: приемка по пустому стеку и приемка по конечному состоянию . Они не эквивалентны для детерминированного автомата с понижающей передачей (хотя они эквивалентны для недетерминированного автомата с понижающей передачей). Языки, принимаемые пустым стеком, — это те языки, которые принимаются конечным состоянием и не имеют префиксов: ни одно слово в языке не является префиксом другого слова в языке.

Обычным критерием приемлемости является конечное состояние , и именно этот критерий приемлемости используется для определения детерминированных контекстно-свободных языков .

Признанные языки

Если $L(A)$ это язык, принимаемый КПК $A$, он также может быть принят DPDA тогда и только тогда, когда существует одно вычисление от исходной конфигурации до принятия одного для всех строк, принадлежащих $L(A)$. Если $L(A)$ может быть принят КПК, это контекстно-свободный язык, а если он может быть принят DPDA, то это детерминированный контекстно-свободный язык (DCFL).

Не все контекстно-свободные языки являются детерминированными. Это делает DPDA строго более слабым устройством, чем КПК. Например, язык L _p четной длины палиндромов в алфавите 0 и 1 имеет контекстно-свободную грамматику S → 0S0 | 1С1 | е. Если DPDA для этого языка существует и видит строку 0 ^н , он должен использовать свой стек для запоминания длины n , чтобы иметь возможность различать возможные продолжения 0 ^н 11 0 ^н ∈ Lp _​ и 0 ^н 11 0 ^{п +2} ∉ Л _п . Следовательно, после прочтения 0 ^н 11 0 ^н , сравнение длины после «11» с длиной до «11» снова сделает стек пустым. По этой причине строки 0 ^н 11 0 ^н 0 ^н 11 0 ^н ∈ Lp _​ и 0 ^н 11 0 ^н 0 ^{п +2} 11 0 ^{п +2} ∉ L _p невозможно различить.

Ограничение DPDA одним состоянием уменьшает класс языков, принимаемых к языкам LL(1) , который является подклассом DCFL. В случае с КПК это ограничение не влияет на класс принимаемых языков.

Характеристики

Закрытие

Свойства замыкания детерминированных контекстно-свободных языков (принимаемых детерминированным КПК по конечному состоянию) радикально отличаются от контекстно-свободных языков. Например, они (фактически) закрыты при дополнении, но не закрыты при объединении. Доказать, что дополнение языка, принимаемое детерминированным КПК, также принимается детерминированным КПК, сложно, поскольку нужно избегать бесконечных вычислений и правильно обрабатывать переходы, которые манипулируют стеком без чтения входных символов.

В результате дополнения можно решить, принимает ли детерминированный КПК все слова из своего входного алфавита, проверив его дополнение на пустоту. Это невозможно для контекстно-свободных грамматик (следовательно, не для обычных КПК).

Проблема эквивалентности

Жеро Сенизерг (1997) доказал, что проблема эквивалентности для детерминированного КПК (т.е. для двух детерминированных КПК A и B является ли L(A)=L(B)?) разрешима, доказательство, которое принесло ему премию Гёделя 2002 года . Для недетерминированного КПК эквивалентность неразрешима.

Дальнейшее чтение

• Гамбургер, Генри; Дана С. Ричардс (2002). Логические и языковые модели для информатики . Река Аппер-Сэдл, Нью-Джерси 07458: Прентис-Холл. стр. 284–331 . ISBN  0-13-065487-6 . {{cite book}}: CS1 maint: местоположение ( ссылка )