Les problèmes suivants sont indécidables:

1. Etant donnée une grammaire générale G et un mot w, est-ce que w \in L\left(G\right)?
2. Etant donnée une grammaire générale G, est-ce que \epsilon \in L\left(G\right)?
3. Etant donnée deux grammaires G_1 et G_2, est-ce que L\left(G_1\right)=L\left(G_2 \right)?
4. Etant donnée une grammaire G, est-ce que L\left(G\right)=\emptyset?
5. Il existe une grammaire générale G_u pour laquelle le problème suivant est indécidable : étant donné w, est-ce que w \in L\left(G_u \right)?

• Ces énoncés sont le pendant exact du théorème d'indécidabilité concernant les MT.
• La preuve provient du fait qu'on a équivalence constructive entre MT et grammaires générales.

Les problèmes suivants concernant les grammaires algébriques (ou “hors contexte”) sont indécidables :

1. étant donnée une grammaire algébrique G, est-ce que L\left(G\right)=\Sigma^* ? (preuve pas facile)
2. étant donnée deux grammaires algébriques G_1 , G_2, est-ce que L\left(G_1\right)=L\left(G_2\right)? [ Même chose avec les automates à pile M1 et M2 : L(M1) = L(M2)? ]
3. étant donné un automate à pile M, trouver un automate à pile M' tel que L(M) = L(M') et M' a un nombre minimal d'états.

1. difficile → admis
2. \Sigma = \left\{ a, b, c \right\}\quad ,\quad G_0:S\rightarrow Sa | Sb | Sc | \epsilon \quad \Rightarrow L\left(G_0\right) = \Sigma^*. Donc si cette deuxième question était décidable on saurait décider le premier problème on comparant le langage L(G) pour une grammaire algébrique et L(G_0)
3. preuve incomplète :
   • Proposition (non démontrée ici) : soit \Sigma un alphabet et M un automate à pile reconnaissant un langage \Sigma^*. Si M a un seul état alors on sait décider si L(M)=\Sigma^* (ou non).
   • Donc, si on savait minimiser un automate à pile, tout automate à pile reconnaissant \Sigma^* serait minimisable en un automate à un état dont on saurait décider s'il accepte (ou non) \Sigma^*. Dans ce cas, le premier problème serait décidable.

Un langage L est récursif si et seulement si L et \bar{L} sont récursivement énumérables.

• L récursif ⇒ récursivement énumérable car on peut (choisir de) faire boucler infiniment en cas de “non”, et \bar{L} et récursivement énumérable en inversant “Y” et “N”
• Il existe M1 qui semi-décide L et M2 qui semi-décide \bar{L}. On considère une machine M à deux rubans.
  • copier ruban 1 (le mot à décider) sur ruban 2
  • faire un pas de M1 sur le ruban 1 et un pas de M2 sur le ruban 2. Si M1 accepte, on accepte; si M2 accepte, on rejette : cette machine décide L.

• On dit qu'une MT énumère le langage L avec l'état q (q \in K) si et seulement si on a
  • L = \left\{w | \left(s, \triangleright \sqcup \right) \vdash_{M}^* \left(q, s \triangleright \sqcup w \right)\right\} .
  • q est appelé l'état d'affichage de M.
• Un langage L est dit Turing énumérable si et seulement si il existe une MT qui l'énumère.

Un langage L est Turing-énumérable ⇔ il est récursivement énumérable.

• Turing énumérable ⇒ récursivement énumérable
  • L est énuméré par M avec l'état d'affichage q. On construit une MT M' qui semi-décide L de la manière suivante– une machine à deux rubans :
  1. déplacer le contenu du ruban 1 sur le ruban 2.
  2. lancer M sur le ruban 1 et, à chaque passage par q, comparer les deux rubans : si égalité, s'arrêter dans l'état “Y”.
• Récursivement énumérable ⇒ Turing énumérable
  • L est semi-décidé par M. On construit M' qui énumère L de la manière suivant :
    1. on sait construire une machine E_{\Sigma} capable de produire tout \Sigma^* dans l'ordre lexicographique.
    2. M' énumère à l'aide de E_{\Sigma} tous les mots de longueur inférieur ou égale à i, à partir de i=0.
    3. pour chacun des mots, on fait i pas de M si possible. Si M s'arrête dans ce calcul on affiche le mot, et on recommence pour i ← i+1.

Montrons que la classe des langages récursifs est stable par …

schémas à faire

II.4 Problèmes Indécidables – III. Complexité