From fb5a8693dbe6a17e9cd6e115d04941c527aee6bc Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Sun, 3 Feb 2019 13:57:05 +0100
Subject: Take into account Antoine's remarks, but they may be too late.
---
controle-20190205.tex | 57 ++++++++++++++++++++++++++++-----------------------
1 file 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'$
--
cgit v1.2.3