Детерминированный автомат выталкивания - Deterministic pushdown automaton

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

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

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

A (не обязательно детерминированный) КПК ${\displaystyle M}$ можно определить как 7-кортеж:

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

куда

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

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

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

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

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

Возможны два критерия приемки: приемка пустой стек и принятие конечное состояние. Эти два не эквивалентны для детерминированного автомата выталкивания (хотя они предназначены для недетерминированного автомата выталкивания). Языки, принятые пустой стек те языки, которые принимаются конечное состояние и без префиксов: ни одно слово в языке не является префиксом другого слова в языке.^{[нужна цитата ]}

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

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

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

Не все контекстно-свободные языки детерминированы. Это делает DPDA строго более слабым устройством, чем КПК. Например, язык L_п четной длины палиндромы в алфавите 0 и 1 имеет контекстно-свободную грамматику S → 0S0 | 1S1 | ε. Если DPDA для этого языка существует, и он видит строку 0^п, он должен использовать свой стек для запоминания длины п, чтобы можно было различить его возможные продолжения 0^п 11 0^п ∈ L_п и 0^п 11 0^п+2 ∉ L_п. Следовательно, после прочтения 0^п 11 0^п, сравнение длины после "11" с длиной до "11" снова сделает стопку пустой. По этой причине струны 0^п 11 0^п 0^п 11 0^п ∈ L_п и 0^п 11 0^п 0^п+2 11 0^п+2 ∉ L_п не отличить.^[2]

Ограничение DPDA одним состоянием снижает класс языков, принятых в LL (1) языки,^[3] который является собственным подклассом DCFL.^[4] В случае КПК это ограничение не влияет на класс принимаемых языков.

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

Закрытие

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

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

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

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

Примечания

1. Майкл Сипсер (1997). Введение в теорию вычислений. PWS Publishing. п.102. ISBN  0-534-94728-X.
2. Хопкрофт, Джон; Раджив Мотвани; Джеффри Уллман (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Эддисон-Уэсли. стр.249 –253.
3. Курки-Суонио, Р. (1969). «Заметки о нисходящих языках». КУСОЧЕК. 9 (3): 225–238. Дои:10.1007 / BF01946814.
4. Rosenkrantz, D. J .; Стернс, Р. Э. (1970). «Свойства детерминированных грамматик сверху вниз». Информация и контроль. 17 (3): 226–256. Дои:10.1016 / с0019-9958 (70) 90446-8. Здесь: с.246–247
5. Sénizergues, Géraud (1997). «Проблема эквивалентности для детерминированных автоматов проталкивания разрешима». Proc. Int. Coll. по автоматам, языкам и программированию (ICALP). Конспект лекций по информатике. 1256. С. 671–681. Дои:10.1007/3-540-63165-8_221. ISBN  978-3-540-63165-1. - Полная версия: Géraud Sénizergues (1997). L(А) = L(B)? (Технический отчет 1161-97). Университет Бордо, ЛаБри.
6. Жеро Сенизерг (2001). «Фундаментальное исследование: L(А) = L(B)? разрешимость вытекает из полных формальных систем ". Теоретическая информатика. 251 (1–2): 1–166. Дои:10.1016 / S0304-3975 (00) 00285-1.
7. Жеро Сенизерг (2002). "L(А) = L(B)? Упрощенное доказательство разрешимости ". Теоретическая информатика. 281 (1–2): 555–608. Дои:10.1016 / S0304-3975 (02) 00027-0.

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

• Гамбург, Генри; Дана Ричардс (2002). Логические и языковые модели для компьютерных наук. Река Аппер Сэдл, штат Нью-Джерси 07458: Prentice Hall. стр.284 –331. ISBN  0-13-065487-6.