summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--controle-20170330.tex66
1 files changed, 35 insertions, 31 deletions
diff --git a/controle-20170330.tex b/controle-20170330.tex
index efb9a34..7054af5 100644
--- a/controle-20170330.tex
+++ b/controle-20170330.tex
@@ -150,7 +150,8 @@ l'automate déterminisé.
(4) Minimiser l'automate $A_3$ obtenu en (3), si nécessaire
(justifier).
-(5) Donner une autre expression rationnelle équivalente à $r$.
+(5) Donner une autre expression rationnelle équivalente à $r$. (On
+pourra utiliser le résultat de la question (4).)
\begin{corrige}
(1) L'automate de Thompson de $r := a^{*}(ba^{*})^{*}$ doit comporter
@@ -286,8 +287,8 @@ peut aussi noter $+$).
\exercice
-À toutes fins utiles, on rappelle qu'un langage « algébrique » est un
-langage engendré par une grammaire hors contexte, et que
+Pour cet exercice, on rappelle qu'un langage \textit{algébrique} est
+un langage engendré par une grammaire hors contexte, et que
l'intersection d'un langage algébrique et d'un langage rationnel est
un langage algébrique.
@@ -311,17 +312,17 @@ engendre bien $L$). En particulier, on retiendra que $L$ est
algébrique (c'est tout ce qui sera nécessaire pour traiter les
questions suivantes).
+Pour les questions (3) à (5), on pourra introduire le langage
+auxiliaire $N$ dénoté par l'expression rationnelle $b^{+} a b^{+} a
+b^{+} a b^{+}$ où on rappelle que $b^{+}$ est une abréviation
+pour $bb^{*}$ (c'est-à-dire $\geq 1$ répétitions de $b$).
+
(3) On \emph{admet}\footnote{Cela pourrait être démontré au moyen du
lemme de pompage pour les langages algébriques, mais ce n'est pas
demandé.} que le langage $M' := \{b^p a b^q a b^p a b^q : p,q>0\}$
n'est pas algébrique. En \emph{déduire} que le langage $L'$ n'est pas
algébrique. Justifier soigneusement.
-Pour cette question et les suivantes, on pourra introduire le langage
-auxiliaire $N$ dénoté par l'expression rationnelle $b^{+} a b^{+} a b^{+}
-a b^{+}$ où $b^{+}$ est une abréviation pour $bb^{*}$ (dénotant au moins
-une répétition de $b$).
-
(4a) Montrer que le langage $M := \{b^p a b^q a b^q a b^p : p,q>0\}$
(noter la différence dans l'ordre des exposants par rapport à $M'$)
n'est pas rationnel.\quad (4b) En \emph{déduire} que le langage $L$
@@ -393,8 +394,8 @@ peuvent comporter que la lettre $b$ : disons $u = b^r$ et $v = b^s$,
et donc $w = b^{k-r-s} a b a b a b^k$ ; la propriété (i) assure $s>0$,
et on a $uv^iw = b^r b^{si} b^{k-r-s} a b a b a b^k = b^{k+s(i-1)} a b
a b a b^k$, censé appartenir à $M$ pour tout $i$ d'après (iii). Or
-dès que $i\neq 1$, ceci clairement une contradiction. Le langage $M$
-n'est donc pas rationnel.
+dès que $i\neq 1$, ceci est clairement une contradiction. Le langage
+$M$ n'est donc pas rationnel.
(4b) De même qu'en (3), le langage $M$ est l'intersection du langage
$L$ avec le langage rationnel $N$ (dénoté par l'expression rationnelle
@@ -458,28 +459,31 @@ semi-décidable ?&oui&oui&oui&oui&oui\\
\exercice
-On rappelle que le \emph{problème de l'arrêt} $H$ est l'ensemble des
-couples $(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 peut éventuellement noter cela :
-$\varphi_e(x)\downarrow$). On rappelle que le problème de l'arrêt $H$
-est semi-décidable mais non décidable (autrement dit, on ne peut pas
-décider à l'avance en temps fini si un programme $e$ donné va terminer
-sur une entrée $x$, mais on peut au moins vérifier que c'est le cas
-quand ça l'est).
+On rappelle que le \textit{problème (ou langage) de l'arrêt} $H$ est
+l'ensemble des couples\footnote{Pour être rigoureux, on a fixé un
+ codage permettant de représenter les programmes $e$, les entrées $x$
+ à ces programmes, et les couples $(e,x)$ comme des mots sur un
+ certain alphabet, par exemple $\Sigma = \{0,1\}$. (Il n'est pas
+ nécessaire de faire apparaître ce codage dans la description des
+ algorithmes 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 rappelle que le problème de l'arrêt $H$ est semi-décidable mais non
+décidable : autrement dit, on ne peut pas décider à l'avance en temps
+fini si un programme $e$ donné va terminer sur une entrée $x$, mais on
+peut au moins vérifier que c'est le cas quand ça l'est.
On définit ici la variante $H'$ suivante du problème de l'arrêt : $H'$
est l'ensemble des couples $(e,x)$ formés d'un programme $e$ et d'une
entrée $x$, tels que l'exécution du programme $e$ sur l'entrée $x$
-termine en temps fini et renvoie la réponse $42$ (si on veut :
-$\varphi_e(x) = 42$). Ainsi, on a $H' \subseteq H$ (ce fait est
-destiner à éclaircir la définition de $H'$ mais n'est pas utile pour
-la suite).
+termine en temps fini et renvoie la réponse $42$. Ainsi, on a $H'
+\subseteq H$ (ce fait est destiner à éclaircir la définition de $H'$
+mais n'est pas utile pour la suite).
(1) Montrer que $H'$ est semi-décidable.
-(2) Montrer que $H'$ n'est pas décidable (pour cela, on cherchera à
-montrer que s'il l'était, $H$ le serait aussi).
+(2) Montrer que $H'$ n'est pas décidable : pour cela, on cherchera à
+montrer que s'il l'était, $H$ le serait aussi.
\begin{corrige}
(1) Le fait que $H'$ soit semi-décidable se montre de la même manière
@@ -505,12 +509,12 @@ Donnés un programme $e$ et une entrée $x$, on peut construire
mêmes opérations que $e$, mais, à la fin, ignore le résultat calculé,
et renvoie toujours $42$. Ainsi, l'exécution de $e'$ sur l'entrée $x$
termine et renvoie $42$ si et seulement si celle de $e$ sur cette même
-entrée termine (et renvoie n'importe quoi) : si on veut,
-$\varphi_{e'}(x)=42 \liff \varphi_e(x)\downarrow$. On peut alors
-utiliser $H'$ — supposé décidable — pour décider si $e'$ termine (sur
-l'entrée $x$) en renvoyant $42$ : comme ceci revient au même que de
-savoir si $e$ termine (sur l'entrée $x$), ceci fournit un moyen pour
-savoir si $e$ termine (sur l'entrée $x$). Autrement dit, on a résolu
+entrée termine (et renvoie n'importe quoi). Comme on a supposé que
+$H'$ était décidable, on peut alors utiliser un algorithme qui le
+décide pour savoir si $e'$ termine (sur l'entrée $x$) en
+renvoyant $42$ : comme ceci revient au même que de savoir si $e$
+termine (sur l'entrée $x$), ceci fournit un moyen pour savoir si $e$
+termine (sur l'entrée $x$). Autrement dit, on a résolu
algorithmiquement le problème de l'arrêt, ce qui est une
contradiction. C'est donc que $H'$ n'était, en fait, pas décidable.
\end{corrige}