summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2017-01-31 17:04:53 +0100
committerDavid A. Madore <david+git@madore.org>2017-02-05 12:40:09 +0100
commit1f9742c720b9c895410785764bfc1c8bcbb59b00 (patch)
tree1284a7bb8da7ae394d2bfdb0b9c1a30979154865
parent8f19ff7b553d51917a8bc449ba4cc49f84d20e3f (diff)
downloadinf105-1f9742c720b9c895410785764bfc1c8bcbb59b00.zip
inf105-1f9742c720b9c895410785764bfc1c8bcbb59b00.tar.gz
inf105-1f9742c720b9c895410785764bfc1c8bcbb59b00.tar.bz2
Add an exercise on computability.
-rw-r--r--controle-20170207.tex131
1 files changed, 131 insertions, 0 deletions
diff --git a/controle-20170207.tex b/controle-20170207.tex
index ac9d9ca..81fea55 100644
--- a/controle-20170207.tex
+++ b/controle-20170207.tex
@@ -400,6 +400,137 @@ qui vérifie cette propriété suivi d'un suffixe quelconque.
\end{corrige}
+%
+%
+%
+
+\exercice
+
+Soit $\Sigma$ un alphabet (fini, non vide) fixé. Les questions
+suivantes sont indépendantes.
+
+(1) Expliquer, au moyen des résultats vus en cours, pourquoi il existe
+un algorithme $A_1$ qui, donnée une expression rationnelle $r$
+sur $\Sigma$, décide si le langage $L_r$ dénoté par $r$ est différent
+du langage $\Sigma^*$ de tous les mots sur $\Sigma$. (Autrement dit,
+l'algorithme $A_1$ doit prendre en entrée une expression rationnelle
+$r$, terminer en temps fini, et répondre « vrai » s'il existe un mot
+$w\in\Sigma^*$ tel que $w\not\in L_r$ et « faux » si $L_r = \Sigma^*$.
+On ne demande pas que l'algorithme soit efficace.)
+
+(2) Expliquer pourquoi il existe un algorithme $A_2$ qui, donnée une
+grammaire hors contexte $G$ sur $\Sigma$, « semi-décide » si le
+langage $L_G$ engendré par $G$ est différent du langage $\Sigma^*$ de
+tous les mots. (« Semi-décider » signifie que l'algorithme $A_2$ doit
+prendre en entrée une grammaire hors contexte $G$, terminer en temps
+fini en répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que
+$w\not\in L_G$, et ne pas terminer — ou éventuellement terminer en
+répondant « faux » — si $L_G = \Sigma^*$.) Indication : on peut
+tester tous les mots possibles.
+
+(3) Expliquer pourquoi il existe un tel algorithme $A_3$ : on lui
+fournit en entrée un algorithme $T$ qui décide un langage $L_T
+\subseteq \Sigma^*$ (c'est-à-dire que $T$ termine toujours en temps
+fini quand on lui présente un mot sur $\Sigma$, et répond « vrai » ou
+« faux », et $L_T$ est le langage des mots sur lesquels il répond
+« vrai »), et l'algorithme $A_3$ doit semi-décider si $L_T$ est
+différent de $\Sigma^*$. (C'est-à-dire que $A_3$ doit terminer en
+répondant « vrai » s'il existe un mot $w\in\Sigma^*$ tel que $w\not\in
+L_T$, et ne pas terminer — ou éventuellement terminer en répondant
+« faux » — si $L_T = \Sigma^*$.) Indication : la même approche permet
+de traiter les questions (2) et (3).
+
+(4) Expliquer pourquoi il n'existe pas d'algorithme $A_4$ qui, dans
+les mêmes conditions que $A_3$, décide (au lieu de seulement
+semi-décider) si $L_T$ est différent de $\Sigma^*$. (C'est-à-dire que
+$A_4$ est censé terminer toujours, et répondre « vrai » s'il existe un
+mot $w\in\Sigma^*$ tel que $w\not\in L_T$, et « faux » si $L_T =
+\Sigma^*$.) Indication : expliquer comment on pourrait utiliser un
+tel $A_4$ pour résoudre le problème de l'arrêt, en cherchant à
+fabriquer un $T$ qui rejette un mot précisément si un programme donné
+s'arrête.
+
+\begin{corrige}
+(1) Donnée une expression rationnelle $r$, on sait qu'on peut
+ algorithmiquement fabriquer un automate fini non-déterministe à
+ transitions spontanées qui reconnaît exactement le langage $L_r$
+ dénoté par $r$, et ensuite éliminer les transitions spontanées et
+ déterminiser l'automate pour obtenir un automate fini déterministe
+ complet reconnaissant $L_r$. Sur un tel automate, savoir si $L_r
+ \neq \Sigma^*$ est trivial : dès lors qu'il existe un état $q$
+ non-final accessible, il existe un mot rejeté par l'automate (i.e.,
+ n'appartenant pas à $L_r$), à savoir le mot lu en suivant les
+ étiquettes d'un chemin quelconque de l'état initial $q_0$
+ jusqu'à $q$, et inversement, si tous les états sont finaux, il est
+ trivial que l'automate accepte tous les mots. (On pouvait aussi
+ minimiser l'automate et le comparer à l'automate minimal trivial qui
+ reconnaît le langage $\Sigma^*$.)
+
+\smallbreak
+
+(2) On sait qu'il existe un algorithme qui, donnée une grammaire
+hors-contexte $G$ et un mot $w$, décide si $w \in L_G$. Pour
+semi-décider s'il existe un $w$ tel que $w \not\in L_G$, il suffit de
+tester tous les mots possibles : plus exactement, on construit un
+algorithme $A_2$ qui effectue une boucle infinie sur tous les
+$w\in\Sigma^*$ (il est évidemment algorithmiquement faisable
+d'énumérer tous les mots sur $\Sigma$) et, pour chacun, teste si $w
+\in L_G$, et si ce n'est pas le cas, termine immédiatement en
+répondant « vrai » (on a trouvé un $w$ n'appartenant pas à $L_G$),
+tandis que si c'est le cas, l'algorithme $A_2$ ne terminera jamais.
+
+\smallbreak
+
+(3) On procède exactement comme en (2) : par hypothèse on dispose d'un
+algorithme $T$ qui, donné un mot $w$, décide si $w \in L_T$. Pour
+semi-décider s'il existe un $w$ tel que $w \not\in L_T$, il suffit de
+tester tous les mots possibles : plus exactement, on construit un
+algorithme $A_3$ qui effectue une boucle infinie sur tous les
+$w\in\Sigma^*$ et, pour chacun, teste si $w \in L_T$ (en lançant
+l'algorithme $T$ qui, par hypothèse, termine toujours), et si ce n'est
+pas le cas, termine immédiatement en répondant « vrai » (on a trouvé
+un $w$ n'appartenant pas à $L_T$), tandis que si c'est le cas,
+l'algorithme $A_3$ ne terminera jamais.
+
+\smallbreak
+
+(4) Supposons par l'absurde qu'on dispose d'un algorithme $A_4$ comme
+on vient de dire, et montrons pour arriver à une contradiction qu'on
+peut s'en servir pour résoudre le problème de l'arrêt. On se donne
+donc un algorithme $S$ et une entrée $x$ de $S$ et on cherche à savoir
+(en utilisant $A_4$) si $S$ termine sur l'entrée $x$. Pour cela, on
+va construire un $T$ auquel appliquer $A_4$.
+
+Voici une solution possible : donné un mot $w \in \Sigma^*$, le
+programme $T$ ne considère que la longueur $|w|$ de $w$, et lance
+(=simule) l'exécution de $S$ sur l'entrée $x$ pour au plus $|w|$
+étapes : si l'exécution termine dans le temps imparti, alors $T$
+rejette le mot $w$, sinon, il l'accepte (dans tous les cas, $T$
+termine et répond « vrai » ou « faux », donc il est une entrée
+légitime à $A_4$). Cette construction fait que $L_T$ rejette un mot
+précisément lorsque $S$ termine sur $x$ : si au contraire $S$ ne
+termine pas sur $x$, alors $L_T = \Sigma^*$. L'utilisation de $A_4$
+sur $T$ permet donc de savoir algorithmiquement si $S$ termine
+sur $x$, ce qui contredit l'indécidabilité du problème de l'arrêt.
+
+Variante de la même idée : on appelle « trace d'exécution » de $S$ sur
+$x$ un mot $w$ qui code le calcul complet de l'exécution de $S$ sur
+$x$ (par exemple, si on voit $S$ comme une machine de Turing, l'état
+courant et le contenu du ruban à chaque étape), du début à l'arrêt.
+Une telle trace d'exécution existe donc précisément si $S$ termine
+sur $x$. Or il est visiblement décidable de savoir si un mot $w$
+donné est une trace d'exécution (il suffit de vérifier qu'à chaque
+étape la machine a bien fait ce qu'elle devait faire). On peut donc
+écrire un algorithme $T$ qui termine toujours et accepte précisément
+les mots qui \emph{ne sont pas} une trace d'exécution de $S$ sur $x$.
+Le fait que $L_T$ soit différent de $\Sigma^*$ signifie alors
+exactement qu'une trace d'exécution existe, donc que $S$ termine
+sur $x$. Ainsi l'utilisation de $A_4$ permet de savoir
+algorithmiquement si $S$ termine sur $x$, ce qui contredit
+l'indécidabilité du problème de l'arrêt.
+\end{corrige}
+
+
%
%