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

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

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

Формальное определение [ править ]

КПК (не обязательно детерминированный) можно определить как набор из семи: ${\ 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 \ дельта \ двоеточие (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}$ $\delta (q,\varepsilon ,x)\not =\emptyset \,$ $\delta \left(q,a,x\right)=\emptyset$ $a\in \Sigma .$

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

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

Распознаваемые языки [ править ]

Если это язык, принятый КПК , он также может быть принят DPDA тогда и только тогда, когда есть одно вычисление от начальной конфигурации до принятия для всех строк, принадлежащих . Если он может быть принят КПК, это контекстно-свободный язык, а если он может быть принят DPDA, то это детерминированный контекстно-свободный язык (DCFL). $L(A)$ $A$ $L(A)$ $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 не могут быть различимы. ^[2]

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

Свойства [ править ]

Закрытие [ править ]

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

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

Проблема эквивалентности [ править ]

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

Примечания [ править ]

^ Майкл Сипсер (1997). Введение в теорию вычислений . PWS Publishing. п. 102 . ISBN 0-534-94728-X.
^ Хопкрофт, Джон ; Раджив Мотвани ; Джеффри Уллман (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Эддисон-Уэсли. стр. 249 -253.
^ Курки-Суонио, Р. (1969). «Заметки о нисходящих языках». БИТ . 9 (3): 225–238. DOI : 10.1007 / BF01946814 .
^ Розенкранц, диджей; Стернс, Р. Э. (1970). «Свойства детерминированных грамматик сверху вниз» . Информация и контроль . 17 (3): 226–256. DOI : 10.1016 / s0019-9958 (70) 90446-8 . Здесь: с.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). Университет Бордо, ЛаБри.
^ Джерод Сенизергс (2001). «Фундаментальное исследование: L ( A ) = L ( B ) - разрешимость результатов из полных формальных систем». Теоретическая информатика . 251 (1–2): 1–166. DOI : 10.1016 / S0304-3975 (00) 00285-1 .
^ Джерод Сенизергс (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.CS1 maint: location (link)

[1] Майкл Сипсер (1997). Введение в теорию вычислений . PWS Publishing. п. 102 . ISBN 0-534-94728-X.

[2] Хопкрофт, Джон ; Раджив Мотвани ; Джеффри Уллман (2001). Введение в теорию автоматов, языки и вычисления (2-е изд.). Эддисон-Уэсли. стр. 249 -253.

[3] Курки-Суонио, Р. (1969). «Заметки о нисходящих языках». БИТ . 9 (3): 225–238. DOI : 10.1007 / BF01946814 .

[4] Розенкранц, диджей; Стернс, Р. Э. (1970). «Свойства детерминированных грамматик сверху вниз» . Информация и контроль . 17 (3): 226–256. DOI : 10.1016 / s0019-9958 (70) 90446-8 . Здесь: с.246–247

[5] 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). Университет Бордо, ЛаБри.

[6] Джерод Сенизергс (2001). «Фундаментальное исследование: L ( A ) = L ( B ) - разрешимость результатов из полных формальных систем». Теоретическая информатика . 251 (1–2): 1–166. DOI : 10.1016 / S0304-3975 (00) 00285-1 .

[7] Джерод Сенизергс (2002). « L ( A ) = L ( B )? Упрощенное доказательство разрешимости». Теоретическая информатика . 281 (1–2): 555–608. DOI : 10.1016 / S0304-3975 (02) 00027-0 .

[1]