Write answers to second exercise.

1 files changed, 144 insertions, 3 deletions

diff --git a/controle-20210618.tex b/controle-20210618.tex
index ea91ea0..7cea2b2 100644
--- a/controle-20210618.tex
+++ b/controle-20210618.tex
@@ -126,7 +126,7 @@ Git: \input{vcline.tex}
 
 Dans cet exercice, on pose $\Sigma = \{a,b\}$.  On considère
 l'expression rationnelle $r := bb{*}a(a|b){*}$, et soit $L := L(r)$ le
-langage qu'elle dénote (autrement dit, c'est le langage constitués des
+langage qu'elle dénote (autrement dit, c'est le langage constitué des
 mots qui commencent par un nombre $\geq 1$ de fois la lettre $b$,
 immédiatement suivis par la lettre $a$, puis n'importe quoi).
 
@@ -287,7 +287,9 @@ vérifient pas $r$).
 Pour procéder à l'algorithme d'élimination des états, on commence par
 donner à l'automate un unique état final sans aucune transition qui en
 part, appelons-le $\infty$.  On peut aussi d'ores et déjà éliminer
-l'état $3$ qui est maintenant inutile :
+l'état $3$ qui est maintenant inutile, et remplacer les deux
+transitions $Z\to Z$ étiquetées $a$ et $b$ par une seule
+étiquetée $a|b$ (ce qui, dans un RNFA, revient au même) :
 \begin{center}
 \begin{tikzpicture}[>=latex,line join=bevel,automaton]
 \node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
@@ -297,7 +299,7 @@ l'état $3$ qui est maintenant inutile :
 \draw[->] (q0) -- node[auto]{$b$} (q1);
 \draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
 \draw[->] (q0) -- node[auto,swap]{$a$} (qZ);
-\draw[->] (qZ) to[loop left] node[auto]{$a,b$} (qZ);
+\draw[->] (qZ) to[loop left] node[auto]{$a|b$} (qZ);
 \draw[->] (q0) -- node[auto]{$\varepsilon$} (final);
 \draw[->] (q1) -- node[auto]{$\varepsilon$} (final);
 \draw[->] (qZ) -- node[auto,below]{$\varepsilon$} (final);
@@ -338,12 +340,45 @@ $S \rightarrow aSbc$, et enfin « $2$ » la règle $S \rightarrow abSc$.
 selon cette grammaire $G$.  (On pourra d'abord lire les questions
 suivantes si on a du mal à trouver comment dériver ce mot.)
 
+\begin{corrige}
+L'arbre d'analyse est le suivant :
+% S<a.b.S<a.S<a.b.c.>b.c.>c.>
+\begin{center}
+\begin{tikzpicture}[line join=bevel,baseline=(S0.base)]
+\node (S0) at (68.750bp,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 (95.000bp,-30.000bp) [draw=none] {$S$};  \draw (S0) -- (S1);
+\node (a1) at (40.000bp,-60.000bp) [draw=none] {$a$};  \draw (S1) -- (a1);
+\node (S2) at (80.000bp,-60.000bp) [draw=none] {$S$};  \draw (S1) -- (S2);
+\node (a2) at (60.000bp,-90.000bp) [draw=none] {$a$};  \draw (S2) -- (a2);
+\node (b1) at (80.000bp,-90.000bp) [draw=none] {$b$};  \draw (S2) -- (b1);
+\node (c0) at (100.000bp,-90.000bp) [draw=none] {$c$};  \draw (S2) -- (c0);
+\node (b2) at (120.000bp,-60.000bp) [draw=none] {$b$};  \draw (S1) -- (b2);
+\node (c1) at (140.000bp,-60.000bp) [draw=none] {$c$};  \draw (S1) -- (c1);
+\node (c2) at (160.000bp,-30.000bp) [draw=none] {$c$};  \draw (S0) -- (c2);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
 On va maintenant montrer que $G$ est inambiguë.
 
 (2) Expliquer pourquoi tout mot non-vide du langage $L := L(G)$
 engendré par $G$ a nécessairement $a$ pour préfixe (i.e., commence par
 la lettre $a$).
 
+\begin{corrige}
+Les trois règles $0,1,2$ ont toutes le terminal $a$ comme premier
+symbole de leur membre de droite.  Le fils le plus à gauche de la
+racine (étiquetée $S$) dans n'importe quel arbre d'analyse selon $G$
+est nécessairement étiqueté $a$, et le mot analysé commence donc
+nécessairement par $a$.  (Si on préfère, toute dérivation selon $G$
+commence par une règle produisant $a$ comme symbole le plus à gauche,
+qui ne peut ensuite jamais être effacé ni réécrit puisqu'il s'agit
+d'un terminal.)
+\end{corrige}
+
 (3) Montrer que tout mot de $L$ dérivé en démarrant
 par\footnote{C'est-à-dire : tout mot $w$ possédant une dérivation
   selon $G$ de la forme $S \Rightarrow aSbc \mathrel{\Rightarrow^*} w$
@@ -355,19 +390,125 @@ par\footnote{C'est-à-dire : tout mot $w$ possédant une dérivation
 de même que tout mot de $L$ dérivé en démarrant par la règle $2$ a
 nécessairement $aba$ comme préfixe.
 
+\begin{corrige}
+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$.)
+
+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
+commence par $a$, si bien que le mot commence par $aba$.
+\end{corrige}
+
 (4) En déduire comment, d'après les premières lettres d'un mot $w$
 de $L$, on peut savoir par quelle règle démarre nécessairement une
 dérivation de $w$ selon $G$ (ou, ce qui revient au même, quels sont
 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 :
+\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
+\item on peut savoir si un mot $w \in L$ appartient à $L_0$, $L_1$
+  ou $L_2$ en regardant s'il commence par $abc$, $aa$ ou $aba$.
+\end{itemize}
+Ce qui répond à la question posée.
+\end{corrige}
+
 (5) Connaissant tous les arbres d'analyse d'un mot $w$ selon $G$,
 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$.
+\end{corrige}
+
 (6) En déduire que tout mot $w \in L$ possède un unique arbre
 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$.)
+
+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)).
+
+Cette démonstration est constructive, c'est-à-dire qu'on a
+l'algorithme suivant qui analyse un mot $w$ :
+\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 sinon, si $w$ commence par $aa$, vérifier qu'il termine par $bc$
+  (sinon terminer 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}'$) ;
+\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
+  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}'$) ;
+\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
+  d'analyse.
+\end{itemize}
+\vskip-\baselineskip\strut
+\end{corrige}
+
 
 %
 %