Re-read and finalize answers to test.

1 files changed, 176 insertions, 96 deletions

diff --git a/controle-20210618.tex b/controle-20210618.tex
index 585b9c1..aa30be9 100644
--- a/controle-20210618.tex
+++ b/controle-20210618.tex
@@ -102,7 +102,7 @@ Durée : 1h30
 Barème \emph{indicatif} : 8+7+5.
 
 \ifcorrige
-Ce corrigé comporte \textcolor{red}{nnn} pages (page de garde incluse).
+Ce corrigé comporte 9 pages (page de garde incluse).
 \else
 Cet énoncé comporte 3 pages (page de garde incluse).
 \fi
@@ -193,7 +193,8 @@ un automate fini \emph{déterministe complet}.
 \begin{corrige}
 L'automate $\mathscr{A}_1$ est déjà déterministe, mais incomplet :
 pour le transformer en automate déterministe complet, on se contente
-de lui ajouter un puits pour obtenir l'automate $\mathscr{A}_2$ :
+pour obtenir l'automate $\mathscr{A}_2$ de lui ajouter un puits vers
+lequel on fait pointer la seule transition manquante :
 \begin{center}
 \begin{tikzpicture}[>=latex,line join=bevel,automaton]
 \node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
@@ -230,11 +231,11 @@ L'automate $\mathscr{A}_2$ est déterministe complet sans état
 inaccessible.  On commence l'algorithme de minimisation en séparant
 les états finaux $\{3,4,5\}$ et non-finaux $\{0,1,2,\bot\}$.  On
 sépare ensuite ces derniers en deux classes, $\{1,2\}$ et $\{0,\bot\}$
-selon que la transition étiquetée $a$ conduit à un état final.  Enfin,
-la transition étiquetée $b$ sépare la classe $\{0,\bot\}$ en deux.
-Finalement, on aboutit aux classes suivantes : $\{0\}$, $\{1,2\}$,
-$\{3,4,5\}$ et $\{\bot\}$, et à l'automate minimal $\mathscr{A}_3$
-suivant :
+selon que la transition étiquetée $a$ conduit à un état final ou non.
+Enfin, la transition étiquetée $b$ sépare la classe $\{0,\bot\}$ en
+deux.  Finalement, on aboutit aux classes suivantes : $\{0\}$,
+$\{1,2\}$, $\{3,4,5\}$ et $\{\bot\}$ (qu'on rebaptise $0,1,3,\bot$
+respectivement), et à l'automate minimal $\mathscr{A}_3$ suivant :
 \begin{center}
 \begin{tikzpicture}[>=latex,line join=bevel,automaton]
 \node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
@@ -394,14 +395,17 @@ nécessairement $aba$ comme préfixe.
 Si dans un arbre d'analyse $\mathscr{T}$ selon $G$ la racine
 (étiquetée $S$) a quatre fils étiquetés $a,S,b,c$ dans cet ordre
 (i.e., en démarrant par la règle $1$), les descendants du deuxième
-fils (celui étiqueté $S$) forment eux-mêmes un arbre d'analyse
-$\mathscr{T}'$ selon $G$, dont le mot analysé $w'$ (d'après la
-question précédente) commence par $a$, si bien que le mot $w = aw'bc$
-analysé par $\mathscr{T}$ commence par $aa$.  (Si on préfère : une
-dérivation de la forme $S \buildrel 1\over\Rightarrow aSbc
-\mathrel{\Rightarrow^*} w$ a nécessairement $w = aw'bc$ où $w'$ est le
-mot obtenu en appliquant les mêmes règles à $S$, qui commence donc
-par $a$, si bien que $w$ commence par $aa$.)
+fils (celui étiqueté $S$, y compris lui-même) forment eux-mêmes un
+arbre d'analyse $\mathscr{T}'$ selon $G$, dont le mot analysé $w'$
+commence par $a$ (d'après la question précédente), si bien que le mot
+$w = aw'bc$ analysé par $\mathscr{T}$ commence par $aa$.  (Avec la
+notation qui sera introduite ci-dessous, on a $\mathscr{T} =
+\mathbf{R}_1(\mathscr{T}')$.)
+
+Si on préfère : une dérivation de la forme $S \buildrel
+1\over\Rightarrow aSbc \mathrel{\Rightarrow^*} w$ a nécessairement $w
+= aw'bc$ où $w'$ est le mot obtenu en appliquant les mêmes règles
+à $S$, qui commence donc par $a$, si bien que $w$ commence par $aa$.
 
 Un raisonnement analogue conduit à conclure que tout mot dérivé en
 démarrant par la règle $2$ a la forme $abw'c$ où $w'\in L$ donc
@@ -415,10 +419,10 @@ les fils de la racine dans tout arbre d'analyse de $w$).
 
 \begin{corrige}
 Si on appelle $L_0,L_1,L_2$ les parties de $L$ constituées des mots
-ayant une dérivation selon $G$ démarrant par les règles $0,1,2$
-respectivement, on a trivialement $L_0 = \{abc\}$ et on vient de voir
-que les mots de $L_1$ ont $aa$ comme préfixe et ceux de $L_2$ ont
-$aba$ comme préfixe.  Notamment :
+ayant (au moins) une dérivation selon $G$ démarrant par les règles
+$0,1,2$ respectivement, on a trivialement $L_0 = \{abc\}$ et on vient
+de voir que les mots de $L_1$ ont $aa$ comme préfixe et ceux de $L_2$
+ont $aba$ comme préfixe.  Notamment :
 \begin{itemize}
 \item $L_0,L_1,L_2$ sont disjoints (i.e., la règle par laquelle
   démarre une dérivation de $w$ est déterminée par $w$), et
@@ -433,22 +437,90 @@ expliquer comment trouver tous les arbres d'analyse du mot $awbc$
 d'une part, et du mot $abwc$ d'autre part.
 
 \begin{corrige}
-Si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$, on obtient
-un arbre d'analyse $\mathscr{T}^\sharp$ de $w^\sharp := awbc$ de la
-façon suivante : les quatre fils de la racine (étiquetée $S$) de
-$\mathscr{T}^\sharp$ sont étiquetés $a,S,b,c$ respectivement (i.e., on
-démarre par la règle $1$), et le second fils (celui étiqueté $S$) a
-pour descendance une copie de $\mathscr{T}$ : ceci forme manifestement
-un arbre d'analyse selon $G$, dont le mot analysé est $w^\sharp :=
-awbc$.  \emph{Réciproquement}, comme $w^\sharp := awbc$ commence
-par $aa$ (i.e., a $aa$ pour préfixe), on vient de voir que toute
-dérivation de ce mot selon $G$ démarre nécessairement par la
-règle $1$, donc a la forme qu'on vient de décrire.  (Autrement dit :
-$\mathscr{T} \mapsto \mathscr{T}^\sharp$ définit une bijection entre
-les arbres d'analyse de $w$ et ceux de $awbc$.)
-
-Les mêmes considérations valent, \textit{mutatis mutandis} pour les
-mots de la forme $w^\flat := abwc$ en commençant par la règle $2$.
+Afin de s'épargner des répétitions fastidieuses, on définit pour toute
+la suite de ce corrigé des notations pour les arbres d'analyse
+selon $G$ démarrant par les règles $0,1,2$ respectivement, à savoir :
+\begin{itemize}
+\item on notera $\mathbf{R}_0$ l'arbre d'analyse associé à la
+  règle $0$, c'est-à-dire l'arbre dont la racine, étiquetée $S$, a
+  exactement trois fils, qui sont des feuilles, et qui sont étiquetés
+  $a,b,c$ dans cet ordre ;
+\item si $\mathscr{T}$ est un arbre d'analyse selon $G$, on notera
+  $\mathbf{R}_1(\mathscr{T})$ l'arbre d'analyse associé à la règle $1$
+  suivie des règles décrites par $\mathscr{T}$, c'est-à-dire l'arbre
+  dont la racine, étiquetée $S$, a exactement quatre fils, étiquetés
+  $a,S,b,c$ dans cet ordre, où le premier et les deux derniers sont
+  des feuilles et où les descendants du second (y compris lui-même)
+  forment une copie de l'arbre d'analyse $\mathscr{T}$ ;
+\item de façon analogue, si $\mathscr{T}$ est un arbre d'analyse
+  selon $G$, on notera $\mathbf{R}_2(\mathscr{T})$ l'arbre d'analyse
+  associé à la règle $2$ suivie des règles décrites par $\mathscr{T}$,
+  c'est-à-dire l'arbre dont la racine, étiquetée $S$, a exactement
+  quatre fils, étiquetés $a,b,S,c$ dans cet ordre, où les deux
+  premiers et le dernier sont des feuilles et où les descendants du
+  troisième (y compris lui-même) forment une copie de l'arbre
+  d'analyse $\mathscr{T}$.
+\end{itemize}
+
+Soit graphiquement :
+\begin{center}
+\begin{tabular}{c|c|c}
+$\mathbf{R}_0$&$\mathbf{R}_1(\mathscr{T})$&$\mathbf{R}_2(\mathscr{T})$\\
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (20.000bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (b0) at (20.000bp,-30.000bp) [draw=none] {$b$};  \draw (S0) -- (b0);
+\node (c0) at (40.000bp,-30.000bp) [draw=none] {$c$};  \draw (S0) -- (c0);
+\end{tikzpicture}
+&
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (30.000bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (S1) at (20.000bp,-30.000bp) [draw,circle] {$\mathscr{T}$};  \draw (S0) -- (S1);
+\node (b0) at (40.000bp,-30.000bp) [draw=none] {$b$};  \draw (S0) -- (b0);
+\node (c0) at (60.000bp,-30.000bp) [draw=none] {$c$};  \draw (S0) -- (c0);
+\end{tikzpicture}
+&
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (30.000bp,0.000bp) [draw=none] {$S$};
+\node (a0) at (0.000bp,-30.000bp) [draw=none] {$a$};  \draw (S0) -- (a0);
+\node (b0) at (20.000bp,-30.000bp) [draw=none] {$b$};  \draw (S0) -- (b0);
+\node (S1) at (40.000bp,-30.000bp) [draw,circle] {$\mathscr{T}$};  \draw (S0) -- (S1);
+\node (c0) at (60.000bp,-30.000bp) [draw=none] {$c$};  \draw (S0) -- (c0);
+\end{tikzpicture}
+\end{tabular}
+\end{center}
+(par exemple, l'arbre d'analyse répondant à la question $1$ est
+l'arbre $\mathbf{R}_2(\mathbf{R}_1(\mathbf{R}_0))$).
+
+Manifestement, tout arbre d'analyse selon $G$ est soit l'arbre
+$\mathbf{R}_0$, soit de la forme $\mathbf{R}_1(\mathscr{T})$ ou
+$\mathbf{R}_2(\mathscr{T})$ avec $\mathscr{T}$ un autre arbre
+(strictement plus petit).
+
+Répondons maintenant à la question posée.
+
+Si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$, alors
+$\mathbf{R}_1(\mathscr{T})$ est un arbre d'analyse de $awbc$ (toujours
+selon $G$).  Mais réciproquement, comme $awbc$ commence par $aa$
+(i.e., a $aa$ pour préfixe), on a vu en (4) que toute dérivation du
+mot $awbc$ selon $G$ démarre nécessairement par la règle $1$,
+c'est-à-dire que tout arbre d'analyse de $awbc$ est de la
+forme $\mathbf{R}_1(\mathscr{T})$, et $\mathscr{T}$ est alors
+uniquement défini (comme ce qui descend du deuxième fils de la
+racine).  Bref : $\mathbf{R}_1$ définit une bijection entre les arbres
+d'analyse de $w$ et ceux de $awbc$.
+
+De même, si $\mathscr{T}$ est un arbre d'analyse de $w$ selon $G$,
+alors $\mathbf{R}_2(\mathscr{T})$ est un arbre d'analyse de $abwc$.
+Mais réciproquement, comme $abwc$ commence par $aba$ (i.e., a $aba$
+pour préfixe), on a vu en (4) que toute dérivation du mot $abwc$
+selon $G$ démarre nécessairement par la règle $2$, c'est-à-dire que
+tout arbre d'analyse de $abwc$ est de la
+forme $\mathbf{R}_2(\mathscr{T})$, et $\mathscr{T}$ est alors
+uniquement défini (comme ce qui descend du troisième fils de la
+racine).  Bref : $\mathbf{R}_2$ définit une bijection entre les arbres
+d'analyse de $w$ et ceux de $awbc$.
 \end{corrige}
 
 (6) En déduire que tout mot $w \in L$ possède un unique arbre
@@ -456,57 +528,60 @@ d'analyse selon $G$, et proposer (sur la base des questions
 précédentes) un algorithme qui le calcule.
 
 \begin{corrige}
-D'après les questions suivantes, tout mot de $L$ est dans un et un
-seul des trois cas suivants : soit c'est le mot $abc$ produit par la
-règle $abc$, soit il commence par $aa$ et c'est un mot de la forme
-$awbc$ produit par une dérivation démarrant par la règle $1$ puis en
-suivant une dérivation de $w$, soit il commence par $aba$ et c'est un
-mot de la forme $abwc$ produit par une dérivation démarrant par la
-règle $2$ puis en suivant une dérivation de $w$.  (Si on veut, $L$ est
-réunion disjointe de $L_0,L_1,L_2$ où $L_0 = \{abc\}$ et $w \mapsto
-awbc$ est une bijection $L \to L_1$ et $w \mapsto abwc$ est une
-bijection $L \to L_2$.)
+En reformulant les conclusions des questions suivantes, tout mot $w$
+de $L$ est dans un et un seul des trois cas suivants :
+\begin{itemize}
+\item soit $w$ est le mot $abc$ et son unique arbre d'analyse selon $G$
+  est $\mathbf{R}_0$,
+\item soit $w$ commence par $aa$ et alors $w$ est de la forme $aw'bc$
+  et tout arbre d'analyse de $w$ selon $G$ est de la forme
+  $\mathbf{R}_1(\mathscr{T}')$ pour un unique arbre d'analyse
+  $\mathscr{T}'$ de $w'$,
+\item soit $w$ commence par $aba$ et alors $w$ est de la forme $abw'c$
+  et tout arbre d'analyse de $w$ selon $G$ est de la forme
+  $\mathbf{R}_2(\mathscr{T}')$ pour un unique arbre d'analyse
+  $\mathscr{T}'$ de $w'$.
+\end{itemize}
 
 Il résulte par récurrence sur la longueur de $w \in L$ que $w$ a un
-unique arbre d'analyse selon $G$ : en effet, il est soit de la forme
-$abc$, soit de la forme $aw'bc$, soit de la forme $abw'c$ avec dans
-les deux derniers cas $|w'| < |w|$ (précisément $|w'| = |w|-3$), donc
-$w'$ a un unique arbre d'anayse selon $G$ par récurrence, d'où il
-résulte que $w$ a un unique arbre d'analyse (qui s'obtient à partir de
-celui de $w'$ en mettant la règle $1$ ou $2$ au sommet comme expliqué
-dans la question (5)).
+unique arbre d'analyse selon $G$ : en effet, dans le premier des trois
+cas ci-dessus, $w$ a pour unique arbre d'analyse $\mathbf{R}_0$, et
+dans les deux derniers cas on a $|w'| < |w|$ (précisément $|w'| =
+|w|-3$), donc $w'$ a un unique arbre d'anayse $\mathscr{T}'$ selon $G$
+par l'hypothèse de récurrence, d'où il résulte que $w$ a lui aussi un
+unique arbre d'analyse (à savoir $\mathbf{R}_1(\mathscr{T}')$ ou
+$\mathbf{R}_2(\mathscr{T}')$).
+
+La grammaire $G$ est donc inambiguë.
 
 Cette démonstration est constructive, c'est-à-dire qu'on a
-l'algorithme suivant qui analyse un mot $w$ :
+l'algorithme suivant qui analyse un mot $w$ et renvoie l'unique arbre
+d'analyse de $w$ selon $G$ (s'il existe, ou signale une erreur
+d'analyse dans le cas contraire) :
 \begin{itemize}
-\item si le mot $w$ à analyser est $abc$, renvoyer l'arbre de la
-  règle $0$ (c'est-à-dire ayant une racine étiquetée $S$ avec trois
-  fils, tous des feuilles, étiquetés $a,b,c$ respectivement) ;
+\item si le mot $w$ à analyser est $abc$, renvoyer l'arbre
+  $\mathbf{R}_0$ ;
 \item sinon, si $w$ commence par $aa$, vérifier qu'il termine par $bc$
-  (sinon terminer avec une erreur d'analyse), appeler $w'$ le mot
+  (sinon abandonner avec une erreur d'analyse), appeler $w'$ le mot
   obtenu en effaçant le $a$ initial et le $bc$ final, appliquer
   récursivement l'algorithme qu'on est en train de définir au
-  mot $w'$, il retourne un arbre d'analyse $\mathscr{T}'$, et renvoyer
-  l'arbre d'analyse $\mathscr{T}$ fabriqué à partir de la règle $1$ et
-  de l'arbre $\mathscr{T}'$ (i.e., les quatre fils de la racine
-  étiquetée $S$ de $\mathscr{T}$ sont étiquetés $a,S,b,c$
-  respectivement, et le second fils a pour descendance une copie
-  de $\mathscr{T}'$) ;
+  mot $w'$, appeler $\mathscr{T}'$ l'arbre d'analyse ainsi calculer,
+  et renvoyer $\mathbf{R}_1(\mathscr{T}')$ ;
 \item sinon, si $w$ commence par $aba$, vérifier qu'il termine par $c$
-  (sinon terminer avec une erreur d'analyse), appeler $w'$ le mot
+  (sinon abandonner avec une erreur d'analyse), appeler $w'$ le mot
   obtenu en effaçant le $ab$ initial et le $c$ final, appliquer
   récursivement l'algorithme qu'on est en train de définir au
-  mot $w'$, il retourne un arbre d'analyse $\mathscr{T}'$, et renvoyer
-  l'arbre d'analyse $\mathscr{T}$ fabriqué à partir de la règle $2$ et
-  de l'arbre $\mathscr{T}'$ (i.e., les quatre fils de la racine
-  étiquetée $S$ de $\mathscr{T}$ sont étiquetés $a,b,S,c$
-  respectivement, et le troisième fils a pour descendance une copie
-  de $\mathscr{T}'$) ;
+  mot $w'$, appeler $\mathscr{T}'$ l'arbre d'analyse ainsi calculer,
+  et renvoyer $\mathbf{R}_2(\mathscr{T}')$ ;
 \item dans tout autre cas (i.e., si $w$ n'est pas $abc$ et commence
-  par autre chose que $aa$ ou $aba$), terminer avec une erreur
+  par autre chose que $aa$ ou $aba$), abandonner avec une erreur
   d'analyse.
 \end{itemize}
-\vskip-\baselineskip\strut
+(L'algorithme termine en temps fini parce que les appels récursifs se
+font sur des mots de longueur strictement plus courte.  Il s'agit d'un
+algorithme par « descente récursive », qui se transforme facilement,
+quitte à remplacer la pile des appels récursifs en une pile en tant
+que structure de données, en un analyseur LL.)
 \end{corrige}
 
 
@@ -530,11 +605,11 @@ semi-décidable ?  On justifiera soigneusement les réponses.
 \begin{corrige}
 Le langage proposé n'est pas rationnel car il n'est pas algébrique.
 
-Il est décidable car il est évident qu'on peut algorithmiquement
-vérifier qu'un mot est de la forme $a^i b^j c^k$ (comme ceci
+Il est décidable car il est évident qu'on peut algorithmiquement d'une
+part vérifier qu'un mot est de la forme $a^i b^j c^k$ (comme ceci
 correspond à l'expression rationnelle $a{*}b{*}c{*}$, c'est faisable
-par automate fini) puis vérifier qu'il a autant de $a$ que de $b$ que
-de $c$.
+par automate fini) et d'autre part vérifier qu'il a autant de $a$ que
+de $b$ que de $c$.
 
 Étant décidable, il est notamment semi-décidable.
 \end{corrige}
@@ -561,28 +636,33 @@ L'ensemble $J$ est-il décidable ?  Semi-décidable ?  On justifiera
 soigneusement.
 
 \begin{corrige}
-L'ensemble $J$ n'est pas semi-décidable.  En effet, supposons par
-l'absurde qu'on dispose d'un algorithme $T$ qui semi-décide $J$ (où
-« semi-décider » un ensemble $Z$ signifie : terminer en renvoyant $1$
-(=vrai) si l'entrée $z$ fournie appartient à $Z$, et ne pas terminer
-sinon).  Fixons une fois pour toutes $f$ (le code d')un programme qui,
-donnée une entrée $x$, termine immédiatement (en ignorant $x$).  Alors
-trivialement $(f,x) \in H$ quel que soit $x$ ; donc, par définition
-de $J$, on a $(f,e,x) \in J$ si et seulement si $(e,h) \not \in H$.
-On dispose alors d'un algorithme $T'$ qui semi-décide le
-complémentaire de $H$, défini de la manière suivante : donnés $(e,x)$,
-on applique l'algorithme $T$ (qu'on a supposé exister) au triplet
-$(f,e,x)$ : si $T$ termine (autrement dit, si $(f,e,x) \in J$), on
-renvoie $1$ (sinon, bien sûr, on ne termine jamais) ; par
+L'ensemble $J$ n'est pas semi-décidable.
+
+Pour le montrer, supposons par l'absurde qu'on dispose d'un algorithme
+$T$ qui semi-décide $J$ (où « semi-décider » un ensemble $Z$
+signifie : terminer en renvoyant $1$ (=vrai) si l'entrée $z$ fournie
+appartient à $Z$, et ne pas terminer sinon).  Fixons une fois pour
+toutes (le code d')un programme $f$ qui, donnée une entrée $x$,
+termine immédiatement (en ignorant $x$).  Alors trivialement $(f,x)
+\in H$ quel que soit $x$ ; donc, par définition de $J$, on a $(f,e,x)
+\in J$ si et seulement si $(e,h) \not \in H$.
+
+On considère alors l'algorithme $T'$, défini de la manière suivante :
+donnés $(e,x)$, on applique l'algorithme $T$ (qu'on a supposé exister)
+au triplet $(f,e,x)$ : si $T$ termine (autrement dit, si $(f,e,x) \in
+J$), on renvoie $1$ (sinon, bien sûr, on ne termine jamais).  Par
 construction, $T'$ termine en renvoyant $1$ sur l'entrée $(e,x)$ si
 $(f,e,x) \in J$, c'est-à-dire $(e,x) \not\in H$, et sinon il ne
-termine pas ; ceci signifie justement que $T'$ semi-décide le
-complémentaire de $H$.  Or le complémentaire de $H$ n'est pas
-semi-décidable (car si le complémentaire de $H$ était semi-décidable,
-on aurait à la fois $H$ et son complémentaire semi-décidables, donc
-$H$ serait décidable, et on sait qu'il ne l'est pas).  C'est une
-contradiction : $J$ n'est donc pas semi-décidable.  \textit{A
-  fortiori}, $J$ n'est pas décidable.
+termine pas.  Ceci signifie que $T'$ semi-décide le complémentaire
+de $H$.
+
+Or le complémentaire de $H$ n'est pas semi-décidable (car si le
+complémentaire de $H$ était semi-décidable, on aurait à la fois $H$ et
+son complémentaire semi-décidables, donc $H$ serait décidable, et on
+sait qu'il ne l'est pas), donc un tel algorithme $T'$ ne peut pas
+exister.  C'est une contradiction : $J$ n'est donc pas semi-décidable.
+
+\textit{A fortiori}, $J$ n'est pas décidable.
 \end{corrige}