Take into account Antoine's remarks, but they may be too late.exam-20190205

1 files changed, 31 insertions, 26 deletions

diff --git a/controle-20190205.tex b/controle-20190205.tex
index c975ab4..6007848 100644
--- a/controle-20190205.tex
+++ b/controle-20190205.tex
@@ -156,7 +156,8 @@ manière seront plus lourdement sanctionnées.)
 (1) Traiter l'une \emph{ou} l'autre des questions suivantes :
 (i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ;
 (ii) construire l'automate de Thompson de $r$, puis éliminer les
-transitions spontanées de ce dernier : on appellera $\mathscr{A}_1$
+transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on
+retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$
 l'automate ainsi obtenu.
 
 (Dans les deux cas, on obtient le même automate $\mathscr{A}_1$, ayant
@@ -551,15 +552,14 @@ que $w$, d'après l'hypothèse de récurrence ils vérifient (A) et (B),
 si bien que $w$ vérifie aussi (A) et (B) d'après la question (4).
 \end{corrige}
 
-(6) Soit $w$ un mot \emph{non vide} vérifiant (A) et (B).
+(6) Soit $w$ un mot \emph{non vide} vérifiant (A) et (B).  \quad
 (6.1) Montrer qu'on peut écrire $w = av$ pour un certain $v \in
-\Sigma^*$.  (6.2) Si $w'$ est le plus long préfixe de $v$
+\Sigma^*$.\quad (6.2) Si $w'$ est le plus long préfixe de $v$
 vérifiant (B)\footnote{Autrement dit, le plus long préfixe $w'$ de $v$
   tel que pour tout préfixe $u'$ de $w'$ (y compris $w'$ lui-même) on
   ait $|u'|_b\leq |u'|_a$.}, montrer qu'on a $w = aw'bw''$ pour un
-certain $w'' \in \Sigma^*$.  (6.3) Montrer que $w'$ vérifie (B).
-(6.4) Montrer que $w'$ vérifie (A).  (6.5) Montrer que $w''$ vérifie
-(A) et (B).
+certain $w'' \in \Sigma^*$.\quad (6.3) Montrer que $w'$ vérifie (A).
+\quad (6.4) Montrer que $w''$ vérifie (A) et (B).
 
 \begin{corrige}
 (6.1) Comme $w$ est un mot non vide, on peut parler de sa première
@@ -579,23 +579,21 @@ vérifie $|va|_b = |v|_b \leq |v|_a < |va|_a$) : on peut donc écrire $v
 = w'bw''$ pour un certain $w''\in\Sigma^*$, c'est-à-dire $w =
 aw'bw''$.
 
-(6.3) Le mot $w'$ vérifie (B) : en effet, si $u'$ est préfixe de $w'$ alors
-$au'$ en est un de $w$, et on a $|u'|_b = |au'|_b \leq |au'|_a =
-1+|u'|_a$.  (6.4) Montrons par l'absurde que $w'$ vérifie (A) : si ce n'est
-pas le cas, comme $|w'|_b \leq |w'|_a$ (par (B), qu'on vient de
-montrer), on a $|w'|_b < |w'|_a$, mais alors $|w'b|_b = |w'|_b + 1
-\leq |w'|_a = |w'b|_a$ donc $w'b$ vérifie encore (B), ce qui contredit
-le fait que $w'$ était \emph{le plus long} préfixe de $v$
-vérifiant (B).  (6.5) Le mot $w''$ vérifie (A) : en effet, on a $|w|_b =
-|w|_a$ (puisque $w$ vérifie (A)), c'est-à-dire $|w'|_b + |w''|_b + 1 =
-|w'|_a + |w''|_a + 1$, et comme on vient de voir que $|w'|_b =
-|w'|_a$, on a aussi $|w''|_b = |w''|_a$.  Enfin, le mot $w''$
-vérifie (B) : en effet, si $u''$ est un préfixe de $w''$ alors
-$aw'bu''$ est un préfixe de $w = aw'bw''$ donc (puisque $w$
-vérifie (B)) on a $|aw'bu''|_b \leq |aw'bu''|_a$, c'est-à-dire $|w'|_b
-+ |u''|_b + 1 \leq |w'|_a + |u''|_a + 1$ donc (toujours puisque
-$|w'|_b = |w'|_a$ qu'on vient de voir) $|u''|_b \leq |u''|_a$ comme
-annoncé.
+(6.3) Montrons par l'absurde que $w'$ vérifie (A) : si ce n'est pas le
+cas, comme $|w'|_b \leq |w'|_a$ (par (B), que vérifie $w'$), on a
+$|w'|_b < |w'|_a$, mais alors $|w'b|_b = |w'|_b + 1 \leq |w'|_a =
+|w'b|_a$ donc $w'b$ vérifie encore (B), ce qui contredit le fait que
+$w'$ était \emph{le plus long} préfixe de $v$ vérifiant (B).
+
+(6.4) Le mot $w''$ vérifie (A) : en effet, on a $|w|_b = |w|_a$
+(puisque $w$ vérifie (A)), c'est-à-dire $|w'|_b + |w''|_b + 1 = |w'|_a
++ |w''|_a + 1$, et comme on vient de voir que $|w'|_b = |w'|_a$, on a
+aussi $|w''|_b = |w''|_a$.  Enfin, le mot $w''$ vérifie (B) : en
+effet, si $u''$ est un préfixe de $w''$ alors $aw'bu''$ est un préfixe
+de $w = aw'bw''$ donc (puisque $w$ vérifie (B)) on a $|aw'bu''|_b \leq
+|aw'bu''|_a$, c'est-à-dire $|w'|_b + |u''|_b + 1 \leq |w'|_a + |u''|_a
++ 1$ donc (toujours puisque $|w'|_b = |w'|_a$ qu'on vient de voir)
+$|u''|_b \leq |u''|_a$ comme annoncé.
 \end{corrige}
 
 (7) Déduire des questions (2) et (6) que tout mot vérifiant (A) et (B)
@@ -671,16 +669,21 @@ $H$ des couples\footnote{Pour être rigoureux, on a fixé un codage
   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 a vu en
-cours que $H$ était semi-décidable mais non décidable.
+cours que $H$ était semi-décidable mais non décidable\footnote{Une
+  variante consiste à considérer l'ensemble des $e$ tels que $e$
+  termine sur l'entrée $e$ : l'ensemble $H$ qu'on vient de définir s'y
+  ramène facilement.}.
 
 On considère l'ensemble $H'$ des triplets $(e_1,e_2,x)$ tels que
 $(e_1,x) \in H$ \emph{ou bien} $(e_2,x) \in H$ (ou les deux).
 Autrement dit, au moins l'un des programmes $e_i$ termine en temps
 fini quand on l'exécute sur l'entrée $x$.
 
-(1) Montrer que $H'$ est semi-décidable.
+(1) L'ensemble $H'$ est-il semi-décidable ?
 
 \begin{corrige}
+Nous allons montrer que $H'$ est semi-décidable.
+
 Considérons l'algorithme suivant : donné en entrée un triplet
 $(e_1,e_2,x)$, on exécute en parallèle, en fournissant à chacun
 l'entrée $x$, les programmes (codés par) $e_1$ et $e_2$ (au moyen
@@ -690,9 +693,11 @@ algorithme termine (en renvoyant « vrai ») si et seulement si
 $(e_1,e_2,x) \in H'$, ce qui montre que $H'$ est semi-décidable.
 \end{corrige}
 
-(2) Montrer que $H'$ n'est pas décidable.
+(2) L'ensemble $H'$ est-il décidable ?
 
 \begin{corrige}
+Nous allons montrer que $H'$ n'est pas décidable.
+
 Supposons par l'absurde qu'il existe un algorithme $T$ qui
 décide $H'$.  Soit $e'$ (le code d')un programme quelconque qui
 effectue une boucle infinie (quelle que soit son entrée) : comme $e'$