summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--controle-20180322.tex39
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}
%