From 6d5d3cd4a38a2b6e26b2243bc2ae993bdcfd6270 Mon Sep 17 00:00:00 2001 From: "David A. Madore" Date: Mon, 29 Jan 2018 11:57:54 +0100 Subject: Write answers to first exercise. --- controle-20180206.tex | 152 +++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 151 insertions(+), 1 deletion(-) 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} + % -- cgit v1.2.3