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

редактировать

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

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

Содержание

1 Формальное определение
2 Распознаваемые языки
3 Свойства
- 3.1 Закрытие
- 3.2 Проблема эквивалентности
4 Примечания
5 Дополнительная литература

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

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

M = (Q, Σ, Γ, Q 0, Z 0, A, δ) {\ Displaystyle M = (Q \,, \ Sigma \,, \ Gamma \,, q_ {0} \,, Z_ {0} \,, A \,, \ delta \,)}

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

где

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

δ: (Q × (Σ ∪ {ε}) × Γ) ⟶ P (Q × Γ ∗) {\ Displaystyle \ дельта \ двоеточие (Q \, \ раз (\ Sigma \, \ чашка \ влево \ {\ varepsilon \, \ right \}) ​​\ times \ Gamma \,) \ longrightarrow {\ mathcal {P}} (Q \ times \ Gamma ^ {*})}

\ delta \ двоеточие (Q \, \ times (\ Sigma \, \ cup \ left \ {\ varepsilon \, \ right \}) ​​\ times \ Gamma \,) \ longrightarrow {\ mathcal {P}} (Q \ times \ Gamma ^ { {*}})

где

∗ {\ displaystyle *}

*

- это звезда Клини, что означает, что

Γ ∗ {\ displaystyle \ Gamma ^ {*}}

\ Gamma ^ {*}

- это «набор всех конечных строк (включая пустая строка

ε {\ displaystyle \ varepsilon}

\ varepsilon

) элементов

Γ {\ displaystyle \ Gamma}

\ Gamma

ε {\ displaystyle \ varepsilon}

\ varepsilon

обозначает пустую строку, а

P (X) {\ displaystyle {\ mathcal {P}} (X)}

{\ mathcal {P}} (X)

- набор мощности набора

X {\ displaystyle X}

X

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

Для любого $q ∈ Q, a ∈ Σ ∪ {ε}, x ∈ Γ {\ displaystyle q \ in Q, a \ in \ Sigma \ cup \ left \ {\ varepsilon \ right \}, x \ in \ Gamma}$ $q \ in Q, a \ in \ Sigma \ cup \ left \ {\ varepsilon \ right \}, x \ in \ Gamma$ , установить $δ (q, a, x) {\ displaystyle \ delta (q, a, x) \,}$ $\ delta (q, a, x) \,$ ha s не более одного элемента.
Для любого $q ∈ Q, x ∈ Γ {\ displaystyle q \ in Q, x \ in \ Gamma}$ $q \ in Q, x \ in \ Gamma$ , если $δ (q, ε, x) ≠ ∅ {\ displaystyle \ delta (q, \ varepsilon, x) \ not = \ emptyset \,}$ $\ delta (q, \ varepsilon, x) \ not = \ emptyset \,$ , тогда $δ (q, a, x) = ∅ {\ displaystyle \ delta \ left (q, a, x \ right) = \ emptyset}$ $\ delta \ left (q, a, x \ right) = \ emptyset$ для каждого $a ∈ Σ. {\ displaystyle a \ in \ Sigma.}$ $a \ in \ Sigma.$

Есть два возможных критерия приемлемости: принятие пустым стеком и принятие окончательным состоянием. Эти два не эквивалентны для детерминированного автомата выталкивания (хотя они предназначены для недетерминированного автомата выталкивания). Языки, принимаемые пустым стеком, - это те языки, которые принимаются конечным состоянием и не содержат префиксов: ни одно слово в языке не является префиксом другого слова в языке.

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

распознаваемых языков

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

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

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

Свойства

Замыкание

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

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

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

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

Примечания

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

Дополнительная литература

Hamburger, Henry; Dana Richards (2002).. Upper Saddle River, NJ 07458: Prentice Hall, стр. 284 –331. ISBN 0-13- 065487-6. CS1 maint: location (link )