Write answers to first exercise.

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}
+
 
 
 %