II.5 Problèmes indécidables pour les grammaires

Théorème

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)?

Preuves

  • 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.

Théorème

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.

Preuves

  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.

II.6 Propriétés des langages récursifs

Théorème

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

Preuve

  • 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.

Définition : énumération

  • 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.

Théorème

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

Preuve

  • 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.

Exercices

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

union

intersection

concaténation

FIXME schémas à faire

Navigation

 
m1ilc/c_et_c_b.txt · Dernière modification: 2010/01/06 21:22 par suitable
 
Sauf mention contraire, le contenu de ce wiki est placé sous la licence suivante :CC Attribution-Noncommercial-Share Alike 3.0 Unported
Recent changes RSS feed Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki