Take into account Antoine's remarks.

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}