Entscheiden Sie, ob eine kontextfreie Sprache von einem deterministischen Pushdown-Automaten akzeptiert werden kann

Bei einer kontextfreien Grammatik G existiert ein nicht deterministischer Pushdown-Automat N, der genau die Sprache akzeptiert, die G akzeptiert. (und umgekehrt)

Es kann auch einen deterministischen Pushdown-Automaten D geben, der genau die Sprache akzeptiert, die auch G akzeptiert. Es kommt auf die Grammatik an.

Mit welchem ​​Algorithmus auf den Produktionen von G können wir feststellen, ob D existiert?

Es gibt keinen Algorithmus, der bei einer kontextfreien Grammatik entscheidet, ob ein DPDA dieselbe Sprache erkennt und berechnet, ob sie existiert.

Denn wenn ein solcher Algorithmus existiert, würden wir in der Lage das zu entscheiden , unentscheidbar Problem der Universalität der eine kontextfreie Grammatik , dh ob eine gegebene kontextfreie Grammatik auf erkennt die ganze Sprache .$G$$Σ$$Σ^*$

Angenommen, es gibt einen solchen Algorithmus . Sei eine kontextfreie Grammatik. Lassen sein . Dann entscheidet der Algorithmus , ob es einen DPDA , der erkennt .$A_{DPDA}$$G$$L$$\mathcal L(G)$$A_{DPDA}$$A$$L$

• Wenn es kein solches DPDA gibt, ist von einem DPDA nicht erkennbar, insbesondere ist es nicht regulär, so dass es nicht .$L$$Σ^*$

• Wenn ein DPDA existiert, können wir entscheiden, ob gleich da die Universalität für DPDAs entscheidbar ist. Warum? Weil:$A$$L$$Σ^*$

  • DPDA-Sprachen werden in Ergänzung geschlossen (da DPDAs deterministisch sind)
  • Leere ist für DPDAs entscheidend (weil es für PDAs ist )

Mit wir einen Algorithmus erstellt, der für jede kontextfreie Grammatik entscheidet, ob , was sich als unmöglich erwiesen hat. Daher existiert nicht.$A_{DPDA}$$L(G)=Σ^*$$G$$A_{DPDA}$