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

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

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

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

Детерминированный КПК должен был бы выбрать позицию, которую он считает средней, в некотором роде, которая зависит только от текущего префикса. Предположим, что является таким DPDA. Для любого пусть ; пусть будет пустым словом, а . Это последовательность палиндромов, каждый из которых является префиксом следующего, так что должен быть в состоянии принятия с пустым стеком после чтения . По принципу голубиной дыры должно быть некоторое такое, что и$A$$k\in\mathbb{N}$$u_k=ab^{2k}a$$v_0$$v_{k+1} = v_ku_kv_k$$A$$q_k$$v_k$$k,l$$k\neq l$$q_k=q_l$(существует конечное число состояний, и поэтому некоторые должны быть «повторно использованы», поскольку существует бесконечное число s). Но тогда не может отличить , который является палиндромом, от , который не является.$k$$A$$v_ku_kv_k$$v_lu_kv_k$

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 .