===== II.5 Problèmes indécidables pour les grammaires ===== ==== Théorème ==== 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)? === 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 : - é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. === Preuves === - 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. ---- ===== 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 : - déplacer le contenu du ruban 1 sur le ruban 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 : - on sait construire une machine \$E_{\Sigma}\$ capable de produire tout \$\Sigma^* \$ dans l'ordre lexicographique. - M' énumère à l'aide de \$E_{\Sigma}\$ tous les mots de longueur inférieur ou égale à i, à partir de i=0. - 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 ==== [[c_et_c_a| ]] -- [[c_et_c_d |]]