Zdecyduj, czy języki bezkontekstowe mogą być akceptowane przez deterministyczny automat przesuwania

Biorąc pod uwagę bezkontekstową gramatykę G, istnieje niedeterministyczny automat pushdown N, który akceptuje dokładnie język, który akceptuje G. (i odwrotnie)

Nie może również istnieć deterministyczny automat ze stosem D, który akceptuje dokładnie język G akceptuje też. To zależy od gramatyki.

Za pomocą jakiego algorytmu produkcji G możemy ustalić, czy D istnieje?

automata context-free pushdown-automata

— Andrew Tomazos
źródło

Nawet jeśli wcześniej wiesz, że istnieje DPDA dla G, nie ma algorytmu do jej znalezienia. Zobacz tutaj .

— sdcvvc

Nie ma algorytmu, który dałby gramatykę bezkontekstową, decydowałby, czy DPDA rozpoznaje ten sam język i oblicza go, jeśli istnieje.

$G$ $Σ$ $Σ^*$

$A_{DPDA}$ $G$ $L$ $\mathcal L(G)$ $A_{DPDA}$ $A$ $L$

Jeśli nie ma takiego DPDA, nie jest rozpoznawany przez DPDA, w szczególności nie jest regularny, więc nie może być . $L$ $Σ^*$
Jeśli istnieje DPDA , możemy zdecydować, czy jest równe ponieważ uniwersalność jest rozstrzygalna dla DPDA. Czemu? Dlatego: $A$ $L$ $Σ^*$
- Języki DPDA są zamknięte pod uzupełnieniem (ponieważ DPDA są deterministyczne)
- pustka jest rozstrzygalna dla DPDA (ponieważ dotyczy PDA )

Za pomocą zbudowaliśmy algorytm decydujący, czy dla dowolnej kontekstowej gramatyki , co okazało się niemożliwe. Dlatego nie istnieje. $A_{DPDA}$ $L(G)=Σ^*$ $G$ $A_{DPDA}$

— jmad
źródło

Σ^{*}

$Σ^∗$

Σ^{*}

$Σ^∗$

Σ^{*}

$Σ^∗$

D

$D$