Почему необходим недетерминизм (автоматы выталкивания вниз)?

9

Хотелось бы знать, почему для распознавания контекстно-свободных языков работают только недетерминированные автоматы push-down (DPA = NPDA). Почему детерминированные автоматы (DPDA) не распознают такие языки?

Reactormonk
источник
10
Язык может быть распознан детерминированным автоматом, если существует некоторая грамматика LR (1) для этого языка. Поскольку существуют контекстно-свободные языки, в которых нет грамматики LR (1), описывающей их, NPDA! = DPDA. Поскольку эти результаты очень хорошо известны и, как правило, рассматриваются в курсе по компиляторам, я не уверен, что это отвечает на ваш вопрос: возможно, вы ищете интуицию за этим фактом?
Алекс тен Бринк
это действительно несколько нелогично, учитывая, что существуют другие ключевые модели, в которых недетерминизм не имеет никакого значения для принимаемых языков - ФШМ и ТМ.
vzn

Ответы:

25

Я не совсем уверен, какой аромат "почему" вы ищете. Одну из причин увеличения мощности при недетерминированности можно увидеть в следующем примере:

Позволять L быть набором палиндромов ww¯по некоторому алфавиту (по крайней мере, из двух символов), где является обратным к . NPDA для этого языка может просто помещать символы в свой стек, а затем в какой-то момент предположить, что он достиг середины ввода и постепенно опустошать стек. Обратите внимание, что условие принятия является чисто экзистенциальным - достаточно, чтобы было правильное предположение о том, что слово должно быть принято.w¯w

Детерминированный КПК должен был бы выбрать позицию, которую он считает средней, в некотором роде, которая зависит только от текущего префикса. Предположим, что является таким DPDA. Для любого пусть ; пусть будет пустым словом, а . Это последовательность палиндромов, каждый из которых является префиксом следующего, так что должен быть в состоянии принятия с пустым стеком после чтения . По принципу голубиной дыры должно быть некоторое такое, что иAkNuk=ab2kav0vk+1=vkukvkAqkvkk,lklqk=ql(существует конечное число состояний, и поэтому некоторые должны быть «повторно использованы», поскольку существует бесконечное число s). Но тогда не может отличить , который является палиндромом, от , который не является.kAvkukvkvlukvk

Клаус Дрегер
источник
0

FA детерминистически или недетерминированно принимает один и тот же язык (т. Е. Regular Lang).

Но в случае PDA , если мы ограничим его детерминированное поведение, он не будет принимать некоторые CFL (CFL без префиксного свойства (кроме RL)).

Почему так?

Рассмотрим пример CFL, у которого нет свойства префикса (свойство префикса lang: ни одна строка не является правильным префиксом другой строки в lang).

L = WWR

например. строки 00 и 0000 . (00 - правильный префикс 0000, поэтому wwr не имеет преф. Свойства).

В 00 часов DPDA перейдет в конечное состояние. Теперь, поскольку у DPDA нет выбора между принятием и непрерывностью , он не может принять 0000 после принятия 00 . Это место, где КПК требует недетерминизма .

Наблюдения : в случае FA, lang (RL) без прив. свойство может быть принято детерминистически (например, строки, начинающиеся с 0). Это показывает, что эффект свойства префикса RL и CFL различен . Разница между детерминизмом и недетерминизмом для КПК порождает новое семейство языков. который принят DPDA. Этот язык называется DCFL .

Сушант Шинде
источник