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?

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 L ( G ) = Σ ∗ dla dowolnej kontekstowej gramatyki G , co okazało się niemożliwe. Dlatego A D P D A nie istnieje.$A_{DPDA}$$L(G)=Σ^*$$G$$A_{DPDA}$