В теории автоматов , A детерминированный магазинный автомат ( DPDA или ДП ) является разновидностью магазинного автомата . Класс детерминированных автоматов выталкивания принимает детерминированные контекстно-свободные языки , надлежащее подмножество контекстно-свободных языков . [1]
Машинные переходы основаны на текущем состоянии и входном символе, а также на текущем самом верхнем символе стека. Символы ниже в стопке не видны и не имеют немедленного эффекта. Действия машины включают толкание, выталкивание или замену вершины стопки. Детерминированный автомат выталкивания имеет не более одного допустимого перехода для одной и той же комбинации входного символа, состояния и символа верхнего стека. В этом его отличие от недетерминированного автомата с выталкиванием вниз.
Формальное определение
КПК (не обязательно детерминированный) можно определить как 7-кортеж:
где
- конечный набор состояний
- конечный набор входных символов
- конечный набор символов стека
- это начальное состояние
- это начальный символ стека
- , где это набор принимающих состояний
- - переходная функция, где
- где это Клини звезда , а это означает , что это "набор всех конечных строк (включая пустую строку) элементов ", обозначает пустую строку , а это набор мощности набора .
M является детерминированным, если он удовлетворяет обоим следующим условиям:
- Для любой , набор имеет не более одного элемента.
- Для любой , если , тогда для каждого
Есть два возможных критерия приемки: прием пустым стеком и прием окончательным состоянием . Эти два не эквивалентны для детерминированного автомата выталкивания (хотя они предназначены для недетерминированного автомата выталкивания). Языки, принимаемые пустым стеком, - это те языки, которые принимаются конечным состоянием и не содержат префиксов: ни одно слово в языке не является префиксом другого слова в языке. [ необходима цитата ]
Обычным критерием приемлемости является конечное состояние , и именно этот критерий приемлемости используется для определения детерминированных контекстно-свободных языков .
Признанные языки
Если это язык, поддерживаемый КПК , он также может быть принят DPDA тогда и только тогда, когда есть одно вычисление от начальной конфигурации до принятия для всех строк, принадлежащих . Если может быть принят КПК, это контекстно-свободный язык, и если он может быть принят DPDA, то это детерминированный контекстно-свободный язык (DCFL).
Не все контекстно-свободные языки детерминированы. Это делает DPDA строго более слабым устройством, чем КПК. Например, язык L p палиндромов четной длины на алфавите 0 и 1 имеет контекстно-свободную грамматику S → 0S0 | 1S1 | ε. Если DPDA для этого языка существует и видит строку 0 n , он должен использовать свой стек для запоминания длины n , чтобы иметь возможность различать его возможные продолжения 0 n 11 0 n ∈ L p и 0 n 11 0 п +2 ∉ L п . Таким образом, после прочтения 0 п 11 0 п , сравнивая пост- «11» длины в пре- «11» , длина составит стек пустой снова. По этой причине строки 0 n 11 0 n 0 n 11 0 n ∈ L p и 0 n 11 0 n 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). Университет Бордо, ЛаБри.
- ^ Géraud Sénizergues (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 ( ссылка )