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

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

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

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

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

${\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 .}$

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

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

Распознанные языки

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

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

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

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

Закрытие

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

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

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

Жеро Сенизерг (1997) доказал, что проблема эквивалентности для детерминированных PDA (т. е. для двух детерминированных PDA A и B, является ли L(A)=L(B)?) разрешимой, ^{[8] [9] [10]} доказательство, которое принесло ему премию Гёделя 2002 года . Для недетерминированных PDA эквивалентность неразрешима.

Примечания

1. Майкл Сипсер (1997). Введение в теорию вычислений . PWS Publishing. стр. 102. ISBN 0-534-94728-X.
2. Солтыс-Кулинич, Майкл (2018). Введение в анализ алгоритмов (3-е изд.). World Scientific. стр. 193, 195. ISBN 9789813235922.
3. Хопкрофт, Джон Э.; Мотвани, Раджив; Ульман, Джеффри Д. (2006). Введение в теорию автоматов, языки и вычисления (3-е изд.). Addison-Wesley. стр. 234, 254. ISBN 0-321-45536-3.
4. Хопкрофт, Джон ; Раджив Мотвани ; Джеффри Ульман (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Addison-Wesley. С. 249–253.
5. Курки-Суонио, Р. (1969). «Заметки о языках сверху вниз». BIT . 9 (3): 225–238. doi :10.1007/BF01946814. S2CID  60912010.
6. Розенкранц, DJ; Стернс, RE (1970). «Свойства детерминированных грамматик сверху вниз». Информация и управление . 17 (3): 226–256. doi : 10.1016/s0019-9958(70)90446-8 .Здесь: стр.246–247
7. Хопкрофт, Джон Э.; Ульман, Джеффри Д. (1969-01-01), "Детерминированные автоматы с магазинной памятью", Формальные языки и их связь с автоматами , США: Addison-Wesley Longman Publishing Co., Inc. , дата обращения 29 мая 2024 г.
8. Sénizergues, Géraud (1997). «Проблема эквивалентности для детерминированных магазинных автоматов разрешима». Proc. Int. Coll. on Automata, Languages, and Programming (ICALP) . Lecture Notes in Computer Science . Vol. 1256. pp. 671–681. doi :10.1007/3-540-63165-8_221. ISBN 978-3-540-63165-1.- Полная версия: Жеро Сенизерг (1997). Л(А) = Л(В)? (Технический отчет 1161-97). Университет Бордо, ЛаБРИ.
9. Жеро Сенизерг (2001). «Фундаментальное исследование: L ( A ) = L ( B )? разрешимость следует из полных формальных систем». Теоретическая информатика . 251 (1–2): 1–166. doi :10.1016/S0304-3975(00)00285-1.
10. Жеро Сенизерг (2002). «L(A) = L(B)? Упрощенное доказательство разрешимости». Теоретическая информатика . 281 (1–2): 555–608. doi : 10.1016/S0304-3975(02)00027-0 .

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

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