summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorDavid A. Madore <david+git@madore.org>2018-01-29 11:57:54 +0100
committerDavid A. Madore <david+git@madore.org>2018-01-29 11:57:54 +0100
commit6d5d3cd4a38a2b6e26b2243bc2ae993bdcfd6270 (patch)
tree43dbe8bf473b88af9541a84105c51d16f956dd9c
parent7bbb8c184c6861d15fe4737e9da6eeefadbbc3ce (diff)
downloadinf105-6d5d3cd4a38a2b6e26b2243bc2ae993bdcfd6270.tar.gz
inf105-6d5d3cd4a38a2b6e26b2243bc2ae993bdcfd6270.tar.bz2
inf105-6d5d3cd4a38a2b6e26b2243bc2ae993bdcfd6270.zip
Write answers to first exercise.
-rw-r--r--controle-20180206.tex152
1 files changed, 151 insertions, 1 deletions
diff --git a/controle-20180206.tex b/controle-20180206.tex
index c18064b..4ea67f4 100644
--- a/controle-20180206.tex
+++ b/controle-20180206.tex
@@ -137,6 +137,15 @@ complémentaire $M := \Sigma^* \setminus L$.
(1) Donner une expression rationnelle dénotant $L$.
+\begin{corrige}
+Le langage des mots contenant deux $a$ consécutifs est dénoté par
+l'expression rationnelle $(a|b){*}\,aa\,(a|b){*}$, et celui des mots
+contenant deux $b$ consécutifs par $(a|b){*}\,bb\,(a|b){*}$. On peut
+donc proposer l'expression rationnelle $(a|b){*}\,aa\,(a|b){*} \; | \;
+(a|b){*}\,bb\,(a|b){*}$ ou encore, si on préfère,
+$(a|b){*}\,(aa|bb)\,(a|b){*}$.
+\end{corrige}
+
(2) Indépendamment de la question (1), expliquer brièvement pourquoi
l'automate $\mathscr{A}_2$ suivant reconnaît le langage $L$ :
@@ -157,18 +166,159 @@ l'automate $\mathscr{A}_2$ suivant reconnaît le langage $L$ :
De quelle sorte d'automate s'agit-il ?
+\begin{corrige}
+Un chemin de l'unique état initial $S$ à l'unique état final $T$ de
+$\mathscr{A}_2$ doit passer soit par l'état $A$ soit par l'état $B$,
+donc la lecture de ses étiquettes contient le facteur $aa$
+(correspondant aux transitions $S\to A$ et $A\to T$) ou $bb$ ; et
+réciproquement, un mot contenant le facteur $aa$ ou $bb$ peut se lire
+en suivant un chemin de $S$ à $T$ dans l'automate (en plaçant le
+facteur $aa$ au niveau des transitions $S\to A$ et $A\to T$ ou de
+façon analogue pour $bb$).
+
+Il s'agit là d'un automate non déterministe (l'état $S$ a plusieurs
+transitions sortantes étiquetées par $a$), mais sans transitions
+spontanées ou en abrégé, NFA.
+\end{corrige}
+
(3) Déterminiser (si nécessaire) l'automate $\mathscr{A}_2$ représenté
en (2) ; on appellera $\mathscr{A}_3$ l'automate résultant.
+\begin{corrige}
+En notant $S$, $SA$, $SB$, $SAT$ et $SBT$ les états de l'automate
+déterministe $\mathscr{A}_3$ qui correspondent aux ensembles d'états
+de l'automate $\mathscr{A}_2$ donnés par les lettres en question, la
+déterminisation conduit à l'automate $\mathscr{A}_3$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$};
+\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$};
+\node (SAT) at (140bp,35bp) [draw,circle,state,final] {$SAT$};
+\node (SBT) at (140bp,-35bp) [draw,circle,state,final] {$SBT$};
+\draw [->] (S) -- node[auto,near end] {$a$} (SA);
+\draw [->] (S) -- node[auto,below] {$b$} (SB);
+\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB);
+\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA);
+\draw [->] (SA) -- node[auto] {$a$} (SAT);
+\draw [->] (SB) -- node[auto,below] {$b$} (SBT);
+\draw [->] (SAT) to[out=300,in=60] node[auto] {$b$} (SBT);
+\draw [->] (SBT) to[out=120,in=240] node[auto] {$a$} (SAT);
+\draw [->] (SAT) to[loop above] node[auto] {$a$} (SAT);
+\draw [->] (SBT) to[loop below] node[auto] {$b$} (SBT);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
(4) Minimiser (si nécessaire) l'automate $\mathscr{A}_3$ obtenu
-en (3) ; on appellera $\mathscr{A}_4$ l'automate résultant.
+en (3) ; on appellera $\mathscr{A}_4$ l'automate minimal (=canonique)
+résultant.
+
+\begin{corrige}
+On part bein d'un automate $\mathscr{A}_3$ déterministe complet sans
+état inaccessible. La première étape de l'algorithme de minimisation
+sépare deux classes d'états : $S,SA,SB$ (non finaux) d'une part et
+$SAT,SBT$ de l'autre. Ensuite on sépare $S$ et $SA$ et $SB$ (car le
+premier ne conduit qu'à des états non finaux, le second conduit à des
+états finaux par la transition étiquetée $a$, et le troisième conduit
+à des états finaux par la transition étiquetée $b$). On obtient
+finalement un automate $\mathscr{A}_4$ à quatre états, qu'on peut
+appeler $S,SA,SB,U$ où $U$ est la classe de $SAT$ et $SBT$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$};
+\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$};
+\node (U) at (140bp,0bp) [draw,circle,state,final] {$U$};
+\draw [->] (S) -- node[auto,near end] {$a$} (SA);
+\draw [->] (S) -- node[auto,below] {$b$} (SB);
+\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB);
+\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA);
+\draw [->] (SA) -- node[auto] {$a$} (U);
+\draw [->] (SB) -- node[auto,below] {$b$} (U);
+\draw [->] (U) to[loop above] node[auto] {$a,b$} (U);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
(5) Construire un automate $\mathscr{A}_5$ reconnaissant le
langage $M$ complémentaire de $L$.
+\begin{corrige}
+On obtient $\mathscr{A}_5$ en échangeant états finaux et non finaux
+dans $\mathscr{A}_4$, c'est-à-dire l'automate $\mathscr{A}_5$
+suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state,final] {$SA$};
+\node (SB) at (70bp,-35bp) [draw,circle,state,final] {$SB$};
+\node (U) at (140bp,0bp) [draw,circle,state] {$U$};
+\draw [->] (S) -- node[auto,near end] {$a$} (SA);
+\draw [->] (S) -- node[auto,below] {$b$} (SB);
+\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB);
+\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA);
+\draw [->] (SA) -- node[auto] {$a$} (U);
+\draw [->] (SB) -- node[auto,below,near end] {$b$} (U);
+\draw [->] (U) to[loop above] node[auto] {$a,b$} (U);
+\end{tikzpicture}
+\end{center}
+(L'état $U$ est maintenant un puits.)
+\end{corrige}
+
(6) En appliquant à $\mathscr{A}_5$ la méthode d'élimination des
états, déterminer une expression rationnelle dénotant le langage $M$.
+\begin{corrige}
+On va manipuler des automates finis à transitions étiquetées par des
+expressions rationnelles (ou « RNFA »). Dans un premier temps, on
+donne à l'automate un unique état final $F$ en faisant pointer vers
+lui une transition spontanée (i.e., étiquetée
+par $\underline{\varepsilon}$) depuis tout état qui était final.
+L'état $U$ peut être éliminé d'emblée puisqu'il est inutile (il n'est
+pas co-accessible : c'est un puits !). On a donc affaire à l'automate
+suivant
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$};
+\node (SB) at (70bp,-35bp) [draw,circle,state] {$SB$};
+\node (F) at (140bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (S) -- node[auto,near end] {$a$} (SA);
+\draw [->] (S) -- node[auto,below] {$b$} (SB);
+\draw [->] (SA) to[out=300,in=60] node[auto] {$b$} (SB);
+\draw [->] (SB) to[out=120,in=240] node[auto] {$a$} (SA);
+\draw [->] (SA) -- node[auto] {$\underline{\varepsilon}$} (F);
+\draw [->] (SB) -- node[auto,below,near end] {$\underline{\varepsilon}$} (F);
+\draw [->] (S) to[out=270,in=90] (0,-30bp) to[out=270,in=270] node[auto,below] {$\underline{\varepsilon}$} (140bp,-30bp) to[in=270,out=90] (F);
+\end{tikzpicture}
+\end{center}
+On élimine maintenant l'état $SB$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (S) at (0bp,0bp) [draw,circle,state,initial] {$S$};
+\node (SA) at (70bp,35bp) [draw,circle,state] {$SA$};
+\node (F) at (140bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (S) -- node[auto,near end] {$a|ba$} (SA);
+\draw [->] (SA) -- node[auto] {$\underline{\varepsilon}|b$} (F);
+\draw [->] (S) to[out=270,in=270] node[auto,below] {$\underline{\varepsilon}|b$} (F);
+\draw [->] (SA) to[loop below] node[auto] {$ba$} (SA);
+\end{tikzpicture}
+\end{center}
+Et l'élimination de l'état $SA$ conduit à l'expression rationnelle
+$\underline{\varepsilon}\,|\,b\,|\penalty0\,(a|ba)(ba){*}(\underline{\varepsilon}|b)$
+(il y a bien sûr toutes sortes d'autres expressions rationnelles
+équivalentes : par exemple, on peut la réécrire comme
+$\underline{\varepsilon}\,|\,b\,|\penalty0\,(\varepsilon|b)a(ba){*}(\underline{\varepsilon}|b)$
+ou encore comme
+$(\varepsilon|b)(\underline{\varepsilon}|a(ba){*}(\underline{\varepsilon}|b))$ ;
+si on avait éliminé l'état $SA$ en premier, on serait plutôt tombé sur
+$\underline{\varepsilon}\,|\,a\,|\penalty0\,(b|ab)(ab){*}(\underline{\varepsilon}|a)$,
+et ainsi de suite).
+\end{corrige}
+
%