summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2021-06-17 19:56:38 +0200
committerDavid A. Madore <david+git@madore.org>2021-06-17 19:56:38 +0200
commit141ac53dbf4bc94ed0ee7d3494cc9f4b5cf8d6a1 (patch)
tree843524f4e8fcb73ec6b27eb4a3e2c1f2208e2a96
parent928749936af9b1e6459419498864300c570613b7 (diff)
downloadinf105-141ac53dbf4bc94ed0ee7d3494cc9f4b5cf8d6a1.tar.gz
inf105-141ac53dbf4bc94ed0ee7d3494cc9f4b5cf8d6a1.tar.bz2
inf105-141ac53dbf4bc94ed0ee7d3494cc9f4b5cf8d6a1.zip
Write answers to second exercise.
-rw-r--r--controle-20210618.tex147
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}
+
%
%