Take into account Antoine's remarks.

1 files changed, 24 insertions, 15 deletions

diff --git a/controle-20180322.tex b/controle-20180322.tex
index 4575bf5..8db45ea 100644
--- a/controle-20180322.tex
+++ b/controle-20180322.tex
@@ -323,6 +323,11 @@ l'expression rationnelle moins compacte
 \underline{\varepsilon}\;|\;(b|c){*}\;|\;(b|c){*}a(a|c){*}\;|\;(b|c){*}a(a|c){*}b(a|b){*}
 \]
 qui est cependant sans doute plus lisible.
+
+\emph{Remarque :} le langage $M$ est aussi dénoté par l'expression
+rationnelle plus simple $(b|c){*}\,(a|c){*}\,(a|b){*}$, mais celle-ci
+ne répond pas à la question car elle ne peut pas s'obtenir par
+élimination des états à partir de $\mathscr{A}_4$.
 \end{corrige}
 
 
@@ -333,7 +338,7 @@ qui est cependant sans doute plus lisible.
 \exercice
 
 Dans cet exercice, on pose $\Sigma = \{a,b\}$.  On appelle $L = L(G)$
-le langage défini par la hors-contexte $G$ d'axiome $S$ et de
+le langage défini par la grammaire hors-contexte $G$ d'axiome $S$ et de
 nonterminaux $N = \{S\}$ sur l'alphabet $\Sigma$ donnée par
 \[
 \begin{aligned}
@@ -462,8 +467,8 @@ explicitera très soigneusement le raisonnement).
 On a vu à la question (3) que $P \subseteq L$ ; il est par ailleurs
 trivial que $P \subseteq M$, et on a donc $P \subseteq L\cap M$.  Mais
 on a vu à la question (4) que $L\cap M \subseteq P$ : on a donc $L\cap
-M \subseteq P$.  Le langage $M$ est rationnel d'après la question (2).
-Si le langage $L$ était lui aussi rationnel, le langage $L\cap M$
+M = P$.  Le langage $M$ est rationnel d'après la question (2).  Si le
+langage $L$ était lui aussi rationnel, le langage $L\cap M$
 (c'est-à-dire $P$) le serait car l'intersection de deux langages
 rationnels est rationnelle.  Or on a vu à la question (5) que $P$
 n'est pas rationnel.  C'est donc que $L$ ne l'est pas.
@@ -479,7 +484,7 @@ n'est pas rationnel.  C'est donc que $L$ ne l'est pas.
 Dans cet exercice, on s'intéresse au langage $L$ formé des
 programmes $e$ (codés, dans un langage Turing-complet fixé quelconque,
 comme des entiers naturels ou comme des mots sur un alphabet fixé sans
-importance) qui, quelle que soit le paramètre $n$ qu'on leur fournit
+importance) qui, quel que soit le paramètre $n$ qu'on leur fournit
 en entrée, terminent en temps fini et retournent la valeur $0$ : soit
 $L = \{e : (\forall n) {\varphi_e(n)\downarrow} = 0\}$.  Si l'on
 préfère, $L$ est l'ensemble de toutes les façons de coder la fonction
@@ -542,11 +547,13 @@ que $L$ est décidable, pas juste semi-décidable.)
 L'argument d'Hippolyte, lui, est correct : il montre que si $L$ était
 semi-décidable, le complémentaire du problème de l'arrêt (l'ensemble
 des $e'$ qui ne terminent jamais) serait semi-décidable, ce qui n'est
-pas le cas.  Parmi les points qui méritent éventuellement d'être
-préciser, on peut mentionner : le fait que $e$ se déduise
-algorithmiquement de $e'$ et $m$ ; et le fait qu'il est
-algorithmiquement possible de lancer l'exécution d'un programme sur
-$n$ étapes (peu importe la définition exacte de « étape » tant que
+pas le cas.  (Le complémentaire du problème de l'arrêt n'est pas
+semi-décidable, car s'il l'était, le problème de l'arrêt serait
+décidable, vu qu'il est déjà semi-décidable.)  Parmi les points qui
+méritent éventuellement d'être précisés, on peut mentionner : le fait
+que $e$ se déduise algorithmiquement de $e'$ et $m$ ; et le fait qu'il
+est algorithmiquement possible de lancer l'exécution d'un programme
+sur $n$ étapes (peu importe la définition exacte de « étape » tant que
 chacune termine à coup sûr en temps fini) et tester si elle est bien
 finie au bout de ce temps.
 \end{corrige}
@@ -594,7 +601,7 @@ détailler les éventuels passages incomplets dans le raisonnement
 correct.
 
 \begin{corrige}
-C'est Patricle qui a raison ($M$ n'est pas semi-décidable).
+C'est Patrocle qui a raison ($M$ n'est pas semi-décidable).
 
 Le raisonnement d'Achille se fonde sur l'idée que le complémentaire de
 « l'ensemble des programmes qui renvoient toujours la valeur $0$ » est
@@ -606,11 +613,13 @@ correct).
 L'argument de Patrocle, lui, est correct : il montre que si $M$ était
 semi-décidable, le complémentaire du problème de l'arrêt (l'ensemble
 des $e'$ qui ne terminent jamais) serait semi-décidable, ce qui n'est
-pas le cas.  On fait appel à des fonctions constantes, et qui ne
-peuvent renvoyer que $0$ ou ne pas terminer, mais ce n'est pas
-spécialement problématique.  Parmi les points qui méritent
-éventuellement d'être préciser, on peut mentionner le fait que $e$ se
-déduise algorithmiquement de $e'$ et $m$.
+pas le cas.  (Le complémentaire du problème de l'arrêt n'est pas
+semi-décidable, car s'il l'était, le problème de l'arrêt serait
+décidable, vu qu'il est déjà semi-décidable.)  On fait appel à des
+fonctions constantes, et qui ne peuvent renvoyer que $0$ ou ne pas
+terminer, mais ce n'est pas spécialement problématique.  Parmi les
+points qui méritent éventuellement d'être précisés, on peut mentionner
+le fait que $e$ se déduise algorithmiquement de $e'$ et $m$.
 \end{corrige}
 
 %