Answers to exercise 1.

1 files changed, 179 insertions, 1 deletions

diff --git a/controle-20180322.tex b/controle-20180322.tex
index 4d3f6fa..8ecc787 100644
--- a/controle-20180322.tex
+++ b/controle-20180322.tex
@@ -26,7 +26,7 @@
 \newcommand\thingy{%
 \refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
 \newcommand\exercice{%
-\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}}
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
 \renewcommand{\qedsymbol}{\smiley}
 %
 \DeclareUnicodeCharacter{00A0}{~}
@@ -134,18 +134,196 @@ L$).
 spontanée, $\mathscr{A}_1$ qui reconnaît le langage $L$.  On
 justifiera rapidement pourquoi l'automate proposé convient.
 
+\begin{corrige}
+On peut proposer l'automate $\mathscr{A}_1$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (70bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (140bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3$};
+\draw [->] (q0) to[loop below] node[auto] {$a,b,c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a,b,c$} (q1);
+\draw [->] (q1) -- node[auto] {$b$} (q2);
+\draw [->] (q2) to[loop below] node[auto] {$a,b,c$} (q2);
+\draw [->] (q2) -- node[auto] {$c$} (q3);
+\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3);
+\end{tikzpicture}
+\end{center}
+Pour se convaincre qu'il convient, on remarque qu'un chemin de
+l'unique état initial ($0$) à l'unique état final ($3$) dans cet
+automate est formé par trois transitions $0\to 1$, $1\to 2$ et $2\to
+3$, étiquetées par les lettres $a$, $b$ et $c$ respectivement,
+intercalées d'un nombre quelconque de transitions d'un état vers
+lui-même, étiquetées par une lettre quelconque : la lecture de ses
+étiquettes donne bien un mot ayant $abc$ comme sous-mot ; et
+réciproquement, tout tel mot étiquette au moins un chemin de $0$ à $3$
+(une fois choisies les lettres $a,b,c$ dans l'ordre qui correspondront
+aux transitions changeant d'état).
+
+\emph{Remarque :} il est correct de donner directement l'automate
+déterministe $\mathscr{A}_2$ représenté ci-dessous (puisque tout NFA
+est, en particulier, un DFA), à condition de justifier proprement
+qu'il convient.
+\end{corrige}
+
 (2) Déterminiser (si nécessaire) l'automate $\mathscr{A}_1$ trouvé
 en (1) ; on appellera $\mathscr{A}_2$ l'automate résultant.
 
+\begin{corrige}
+En notant $0':=\{0\}$, $1' := \{0,1\}$, $2' := \{0,1,2\}$ et $3' :=
+\{0,1,2,3\}$ les états de l'automate déterministe $\mathscr{A}_2$ qui
+correspondent aux ensembles d'états de l'automate $\mathscr{A}_1$
+qu'on vient d'indiquer, la déterminisation conduit à l'automate
+$\mathscr{A}_1$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0'$};
+\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$};
+\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$};
+\node (q3) at (210bp,0bp) [draw,circle,state,final] {$3'$};
+\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1);
+\draw [->] (q1) -- node[auto] {$b$} (q2);
+\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2);
+\draw [->] (q2) -- node[auto] {$c$} (q3);
+\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
 (3) Minimiser (si nécessaire) l'automate $\mathscr{A}_2$ obtenu
 en (2) ; on appellera $\mathscr{A}_3$ l'automate minimal (=canonique)
 résultant.
 
+\begin{corrige}
+On part bien d'un automate $\mathscr{A}_2$ déterministe complet sans
+état inaccessible.  La première étape de l'algorithme de minimisation
+sépare deux classes d'états : $0',1',2'$ (non finaux) d'une part et
+$3'$ (finaux) de l'autre.  Ensuite on sépare $0',1'$ d'une part et
+$2'$ de l'autre (car les premiers ne conduisent qu'à des états non
+finaux, tandis que $2'$ conduit à un état final par la transition
+étiquetée $c$).  L'étape suivante sépare $0'$ et $1'$ (car le premier
+ne conduit qu'à un état de la classe $0',1'$ de l'étape précédente,
+tandis que $1'$ conduit à un état de la classe $2'$ par la transition
+étiquetée $b$).  On a donc séparé tous les états, ce qui montre que
+$\mathscr{A}_3 = \mathscr{A}_2$ est minimal.
+
+\emph{Remarque :} on pouvait aussi invoquer l'argument suivant :
+puisque le mot $abc$ doit être accepté et qu'aucun de ses sous-mots
+stricts ne l'est (ce qui exclut qu'il y ait une boucle dans le chemin
+d'acceptation), il faut au moins $|abc|+1 = 4$ états dans n'importe
+quel automate reconnaissant $L$.  Comme $\mathscr{A}_2$ a
+effectivement $4$ états, il est forcément minimal.
+\end{corrige}
+
 (4) Construire un automate $\mathscr{A}_4$ reconnaissant le langage $M
 := \Sigma^*\setminus L$ complémentaire de $L$.
 
+\begin{corrige}
+On obtient $\mathscr{A}_4$ en échangeant états finaux et non finaux
+dans $\mathscr{A}_3 = \mathscr{A}_2$, c'est-à-dire l'automate
+$\mathscr{A}_3$ suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting above] {$0'$};
+\node (q1) at (70bp,0bp) [draw,circle,state,final,accepting above] {$1'$};
+\node (q2) at (140bp,0bp) [draw,circle,state,final,accepting above] {$2'$};
+\node (q3) at (210bp,0bp) [draw,circle,state] {$3'$};
+\draw [->] (q0) to[loop below] node[auto] {$b,c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a,c$} (q1);
+\draw [->] (q1) -- node[auto] {$b$} (q2);
+\draw [->] (q2) to[loop below] node[auto] {$a,b$} (q2);
+\draw [->] (q2) -- node[auto] {$c$} (q3);
+\draw [->] (q3) to[loop below] node[auto] {$a,b,c$} (q3);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
 (5) En appliquant à $\mathscr{A}_4$ la méthode d'élimination des
 états, déterminer une expression rationnelle dénotant le langage $M$.
+(Si on souhaite obtenir une expression plus compacte, il est
+recommandé de commencer l'élimination des états par ceux qui sont
+plutôt proches de l'état final.)
+
+\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, et un
+unique état initial $I$ depuis lequel on fait partir une transition
+spontanée vers $0$.  L'état $3'$ peut être éliminé d'emblée puisqu'il
+est inutile (il n'est pas co-accessible : c'est un puits !).  Par
+ailleurs, deux transitions entre les mêmes états sont remplacées par
+une seule étiquetée par la disjonction des étiquettes (par exemple,
+les deux transitions $0'\to 0'$ étiquetées $b,c$ sont remplacées par
+une seule étiquetée $b|c$).  On a donc affaire à l'automate suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$};
+\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$};
+\node (q2) at (140bp,0bp) [draw,circle,state] {$2'$};
+\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0);
+\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1);
+\draw [->] (q1) -- node[auto] {$b$} (q2);
+\draw [->] (q2) to[loop below] node[auto] {$a|b$} (q2);
+\draw [->] (q2) -- node[auto] {$\underline{\varepsilon}$} (qF);
+\draw [->] (q1) to[out=45,in=135] node[auto] {$\underline{\varepsilon}$} (qF);
+\draw [->] (q0) to[out=90,in=180] (70bp,60bp) to node[auto] {$\underline{\varepsilon}$} (140bp,60bp) to[out=0,in=90] (qF);
+\end{tikzpicture}
+\end{center}
+On élimine maintenant l'état $2'$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$};
+\node (q1) at (70bp,0bp) [draw,circle,state] {$1'$};
+\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0);
+\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0);
+\draw [->] (q0) -- node[auto] {$a$} (q1);
+\draw [->] (q1) to[loop below] node[auto] {$a|c$} (q1);
+\draw [->] (q1) -- node[auto] {$\underline{\varepsilon}|b(a|b){*}$} (qF);
+\draw [->] (q0) to[out=90,in=180] (70bp,40bp) to node[auto] {$\underline{\varepsilon}$} (140bp,40bp) to[out=0,in=90] (qF);
+\end{tikzpicture}
+\end{center}
+(on a fait usage du fait évident que l'expression rationnelle
+$r\underline{\varepsilon}$ est équivalente à $r$).  On élimine
+ensuite l'état $1'$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (qI) at (-70bp,0bp) [draw,circle,state,initial] {$I$};
+\node (q0) at (0bp,0bp) [draw,circle,state] {$0'$};
+\node (qF) at (210bp,0bp) [draw,circle,state,final] {$F$};
+\draw [->] (qI) -- node[auto] {$\underline{\varepsilon}$} (q0);
+\draw [->] (q0) to[loop below] node[auto] {$b|c$} (q0);
+\draw [->] (q0) -- node[auto] {$\underline{\varepsilon}|a(a|c){*}(\underline{\varepsilon}|b(a|b){*})$} (qF);
+\end{tikzpicture}
+\end{center}
+Enfin, l'élimination de l'état $0'$ conduit au RNFA ayant seulement
+deux états $I$ et $F$ reliés par une transition étiquetée par
+\[
+(b|c){*}\Big(\underline{\varepsilon}|a(a|c){*}\big(\underline{\varepsilon}|b(a|b){*}\big)\Big)
+\]
+qui est l'expression rationnelle recherchée (dénotant $M$).
+
+L'élimination des états dans l'ordre $0',1',2'$ conduirait à
+l'expression rationnelle moins compacte
+\[
+\underline{\varepsilon}\;|\;(b|c){*}\;|\;(b|c){*}a(a|c){*}\;|\;(b|c){*}a(a|c){*}b(a|b){*}
+\]
+qui est cependant sans doute plus lisible.
+\end{corrige}
 
 
 %