diff options
| -rw-r--r-- | controle-20180322.tex | 39 |
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} % |