diff options
| -rw-r--r-- | controle-20210618.tex | 147 |
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} + % % |