Dlaczego niezbędny jest niedeterminizm (automaty obniżające)?

Chciałbym wiedzieć, dlaczego do rozpoznawania języków bezkontekstowych działają tylko niedeterministyczne automaty wypychające (DPA = NPDA). Dlaczego deterministyczne automaty wypychające (DPDA) nie rozpoznają takich języków?

Nie jestem do końca pewien, jakiego smaku „dlaczego” szukasz. Jednym z powodów wzrostu mocy przy dopuszczaniu niedeterminizmu jest następujący przykład:

Pozwolić $L$ być zestawem palindromów $w\bar{w}$ nad jakimś alfabetem (co najmniej dwóch symboli), gdzie $\bar{w}$ jest odwrotnością $w$. NPDA dla tego języka może po prostu wypychać symbole na stos, a następnie w pewnym momencie zgadnąć, że osiągnął środek wejścia i stopniowo opróżniał stos. Zauważ, że warunek akceptacji jest czysto egzystencjalny - wystarczy, aby poprawnie zgadnąć słowo.

Deterministyczny PDA musiałby wybrać pozycję, którą uważa za środkową, w sposób zależny tylko od bieżącego prefiksu. Założyć$A$jest takim DPDA. Dla każdego$k\in\mathbb{N}$, pozwolić $u_k=ab^{2k}a$; pozwolić$v_0$ być pustym słowem i $v_{k+1} = v_ku_kv_k$. Jest to sekwencja palindromów, z których każdy jest prefiksem następnego, więc$A$ musi być w stanie akceptacji $q_k$, z pustym stosem, po przeczytaniu $v_k$. Zgodnie z zasadą gołębnicy musi być kilka$k,l$ takie, że $k\neq l$ i $q_k=q_l$ (istnieje skończona liczba stanów, a więc niektóre muszą zostać „ponownie wykorzystane”, ponieważ istnieje nieskończona liczba stanów $k$s). Ale wtedy$A$ nie mogę odróżnić $v_ku_kv_k$, który jest palindromem, z $v_lu_kv_k$, co nie jest.

FA deterministycznie lub niedeterministycznie akceptuje ten sam język (tj. Regularny Lang).

Ale w przypadku PDA , jeśli ograniczymy go do zachowania deterministycznego , nie zaakceptuje niektórych CFL (CFL bez właściwości prefiksu (z wyjątkiem RL)).

Dlaczego tak?

Rozważ przykład CFL, który nie ma właściwości przedrostka (właściwość Przedrostek języka: żaden ciąg nie jest poprawnym przedrostkiem innego łańcucha w języku).

L = wwr

na przykład. ciągi 00 i 0000 . (00 jest poprawnym prefiksem 0000, więc wwr nie ma właściwości pref.).

Zdarza się, że 00 DPDA przejdzie do stanu końcowego. Teraz, ponieważ DPDA nie ma wyboru między akceptacją a ciągłością , nie może zaakceptować 0000 po zaakceptowaniu 00 . To jest miejsce, w którym PDA wymaga niedeterminizmu .

Uwagi : W przypadku FA, lang (RL) bez pref. właściwość może zostać przyjęta deterministycznie (np. ciągi zaczynające się od 0). To pokazuje, że wpływ właściwości prefiksu RL i CFL jest inny . Różnica między determinizmem a niedeterminizmem w PDA powoduje powstanie nowej rodziny języków. który jest akceptowany przez DPDA. Ten język nazywa się DCFL .