Les problèmes suivants sont indécidables:
Etant donnée une grammaire générale G et un mot w, est-ce que w \in L\left(G\right)?
Etant donnée une grammaire générale G, est-ce que \epsilon \in L\left(G\right)?
Etant donnée deux grammaires G_1 et G_2, est-ce que L\left(G_1\right)=L\left(G_2 \right)?
Etant donnée une grammaire G, est-ce que L\left(G\right)=\emptyset?
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)?
Les problèmes suivants concernant les grammaires algébriques (ou “hors contexte”) sont indécidables :
étant donnée une grammaire algébrique G, est-ce que L\left(G\right)=\Sigma^* ? (preuve pas facile)
é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)? ]
é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.
difficile → admis
\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)
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.
Un langage L est Turing-énumérable ⇔ il est récursivement énumérable.
Montrons que la classe des langages récursifs est stable par …
schémas à faire