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

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

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

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

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

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

где

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

${\ displaystyle \ delta \ двоеточие (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 \ дельта (д, а, х) \,}$
• Для любого , если , то для каждого${\ displaystyle q \ in Q, x \ in \ Gamma}$${\ Displaystyle \ дельта (д, \ varepsilon, х) \ not = \ emptyset \,}$${\ Displaystyle \ дельта \ влево (д, а, х \ вправо) = \ emptyset}$${\ displaystyle a \ in \ Sigma.}$

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

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

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

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

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

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

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

Закрытие

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

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

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

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

Заметки

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

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