Décidez si un langage sans contexte peut être accepté par un automate déterministe pushdown

Étant donné une grammaire sans contexte G, il existe un automate N non déterministe à refoulement qui accepte exactement le langage que G accepte. (et vice versa)

Il peut également exister un automate déterministe à refoulement qui accepte exactement le langage que G accepte également. Cela dépend de la grammaire.

Par quel algorithme sur les productions de G peut-on déterminer si D existe?

Il n'y a pas d'algorithme qui, étant donné une grammaire sans contexte, décide si un DPDA reconnaît le même langage et le calcule s'il existe.

Parce que si un tel algorithme existait, nous serions en mesure de décider du problème indécidable de l'universalité d'un contexte sans grammaire -à- dire si une grammaire sans contexte donné sur Σ reconnaît toute la langue .$G$$Σ$$Σ^*$

Supposons qu'il existe un tel algorithme . Soit une grammaire sans contexte. Laissez soit . Ensuite , l'algorithme décidera s'il y a un DPDA A reconnaissant .$A_{DPDA}$$G$$L$$\mathcal L(G)$$A_{DPDA}$$A$$L$

• S'il n'y a pas un tel DPDA, alors n'est pas reconnaissable par un DPDA, en particulier il n'est pas régulier, il ne peut donc pas être .$L$$Σ^*$

• Si un DPDA existe, nous pouvons décider si est égal à car l'universalité est décidable pour les DPDA. Pourquoi? Car:$A$$L$$Σ^*$

  • Les langues DPDA sont fermées par complémentation (car les DPDA sont déterministes)
  • le vide est décidable pour les DPDA (car c'est pour les PDA )

En utilisant nous avons construit un algorithme pour décider si pour une grammaire sans contexte , ce qui s'est avéré impossible. Par conséquent$A_{DPDA}$$L(G)=Σ^*$$G$$A_{DPDA}$ n'existe pas.