diff options
| -rw-r--r-- | controle-20170330.tex | 66 |
1 files changed, 35 insertions, 31 deletions
diff --git a/controle-20170330.tex b/controle-20170330.tex index efb9a34..7054af5 100644 --- a/controle-20170330.tex +++ b/controle-20170330.tex @@ -150,7 +150,8 @@ l'automate déterminisé. (4) Minimiser l'automate $A_3$ obtenu en (3), si nécessaire (justifier). -(5) Donner une autre expression rationnelle équivalente à $r$. +(5) Donner une autre expression rationnelle équivalente à $r$. (On +pourra utiliser le résultat de la question (4).) \begin{corrige} (1) L'automate de Thompson de $r := a^{*}(ba^{*})^{*}$ doit comporter @@ -286,8 +287,8 @@ peut aussi noter $+$). \exercice -À toutes fins utiles, on rappelle qu'un langage « algébrique » est un -langage engendré par une grammaire hors contexte, et que +Pour cet exercice, on rappelle qu'un langage \textit{algébrique} est +un langage engendré par une grammaire hors contexte, et que l'intersection d'un langage algébrique et d'un langage rationnel est un langage algébrique. @@ -311,17 +312,17 @@ engendre bien $L$). En particulier, on retiendra que $L$ est algébrique (c'est tout ce qui sera nécessaire pour traiter les questions suivantes). +Pour les questions (3) à (5), on pourra introduire le langage +auxiliaire $N$ dénoté par l'expression rationnelle $b^{+} a b^{+} a +b^{+} a b^{+}$ où on rappelle que $b^{+}$ est une abréviation +pour $bb^{*}$ (c'est-à-dire $\geq 1$ répétitions de $b$). + (3) On \emph{admet}\footnote{Cela pourrait être démontré au moyen du lemme de pompage pour les langages algébriques, mais ce n'est pas demandé.} que le langage $M' := \{b^p a b^q a b^p a b^q : p,q>0\}$ n'est pas algébrique. En \emph{déduire} que le langage $L'$ n'est pas algébrique. Justifier soigneusement. -Pour cette question et les suivantes, on pourra introduire le langage -auxiliaire $N$ dénoté par l'expression rationnelle $b^{+} a b^{+} a b^{+} -a b^{+}$ où $b^{+}$ est une abréviation pour $bb^{*}$ (dénotant au moins -une répétition de $b$). - (4a) Montrer que le langage $M := \{b^p a b^q a b^q a b^p : p,q>0\}$ (noter la différence dans l'ordre des exposants par rapport à $M'$) n'est pas rationnel.\quad (4b) En \emph{déduire} que le langage $L$ @@ -393,8 +394,8 @@ peuvent comporter que la lettre $b$ : disons $u = b^r$ et $v = b^s$, et donc $w = b^{k-r-s} a b a b a b^k$ ; la propriété (i) assure $s>0$, et on a $uv^iw = b^r b^{si} b^{k-r-s} a b a b a b^k = b^{k+s(i-1)} a b a b a b^k$, censé appartenir à $M$ pour tout $i$ d'après (iii). Or -dès que $i\neq 1$, ceci clairement une contradiction. Le langage $M$ -n'est donc pas rationnel. +dès que $i\neq 1$, ceci est clairement une contradiction. Le langage +$M$ n'est donc pas rationnel. (4b) De même qu'en (3), le langage $M$ est l'intersection du langage $L$ avec le langage rationnel $N$ (dénoté par l'expression rationnelle @@ -458,28 +459,31 @@ semi-décidable ?&oui&oui&oui&oui&oui\\ \exercice -On rappelle que le \emph{problème de l'arrêt} $H$ est l'ensemble des -couples $(e,x)$ formés d'un programme (=algorithme) $e$ et d'une -entrée $x$, tels que l'exécution du programme $e$ sur l'entrée $x$ -termine en temps fini (on peut éventuellement noter cela : -$\varphi_e(x)\downarrow$). On rappelle que le problème de l'arrêt $H$ -est semi-décidable mais non décidable (autrement dit, on ne peut pas -décider à l'avance en temps fini si un programme $e$ donné va terminer -sur une entrée $x$, mais on peut au moins vérifier que c'est le cas -quand ça l'est). +On rappelle que le \textit{problème (ou langage) de l'arrêt} $H$ est +l'ensemble des couples\footnote{Pour être rigoureux, on a fixé un + codage permettant de représenter les programmes $e$, les entrées $x$ + à ces programmes, et les couples $(e,x)$ comme des mots sur un + certain alphabet, par exemple $\Sigma = \{0,1\}$. (Il n'est pas + nécessaire de faire apparaître ce codage dans la description des + algorithmes proposés, qui peut rester informelle.)} $(e,x)$ formés +d'un programme (=algorithme) $e$ et d'une entrée $x$, tels que +l'exécution du programme $e$ sur l'entrée $x$ termine en temps fini. +On rappelle que le problème de l'arrêt $H$ est semi-décidable mais non +décidable : autrement dit, on ne peut pas décider à l'avance en temps +fini si un programme $e$ donné va terminer sur une entrée $x$, mais on +peut au moins vérifier que c'est le cas quand ça l'est. On définit ici la variante $H'$ suivante du problème de l'arrêt : $H'$ est l'ensemble des couples $(e,x)$ formés d'un programme $e$ et d'une entrée $x$, tels que l'exécution du programme $e$ sur l'entrée $x$ -termine en temps fini et renvoie la réponse $42$ (si on veut : -$\varphi_e(x) = 42$). Ainsi, on a $H' \subseteq H$ (ce fait est -destiner à éclaircir la définition de $H'$ mais n'est pas utile pour -la suite). +termine en temps fini et renvoie la réponse $42$. Ainsi, on a $H' +\subseteq H$ (ce fait est destiner à éclaircir la définition de $H'$ +mais n'est pas utile pour la suite). (1) Montrer que $H'$ est semi-décidable. -(2) Montrer que $H'$ n'est pas décidable (pour cela, on cherchera à -montrer que s'il l'était, $H$ le serait aussi). +(2) Montrer que $H'$ n'est pas décidable : pour cela, on cherchera à +montrer que s'il l'était, $H$ le serait aussi. \begin{corrige} (1) Le fait que $H'$ soit semi-décidable se montre de la même manière @@ -505,12 +509,12 @@ Donnés un programme $e$ et une entrée $x$, on peut construire mêmes opérations que $e$, mais, à la fin, ignore le résultat calculé, et renvoie toujours $42$. Ainsi, l'exécution de $e'$ sur l'entrée $x$ termine et renvoie $42$ si et seulement si celle de $e$ sur cette même -entrée termine (et renvoie n'importe quoi) : si on veut, -$\varphi_{e'}(x)=42 \liff \varphi_e(x)\downarrow$. On peut alors -utiliser $H'$ — supposé décidable — pour décider si $e'$ termine (sur -l'entrée $x$) en renvoyant $42$ : comme ceci revient au même que de -savoir si $e$ termine (sur l'entrée $x$), ceci fournit un moyen pour -savoir si $e$ termine (sur l'entrée $x$). Autrement dit, on a résolu +entrée termine (et renvoie n'importe quoi). Comme on a supposé que +$H'$ était décidable, on peut alors utiliser un algorithme qui le +décide pour savoir si $e'$ termine (sur l'entrée $x$) en +renvoyant $42$ : comme ceci revient au même que de savoir si $e$ +termine (sur l'entrée $x$), ceci fournit un moyen pour savoir si $e$ +termine (sur l'entrée $x$). Autrement dit, on a résolu algorithmiquement le problème de l'arrêt, ce qui est une contradiction. C'est donc que $H'$ n'était, en fait, pas décidable. \end{corrige} |