Write answers to first exercise.

1 files changed, 147 insertions, 0 deletions

diff --git a/controle-20210618.tex b/controle-20210618.tex
index a2bf362..ea91ea0 100644
--- a/controle-20210618.tex
+++ b/controle-20210618.tex
@@ -135,6 +135,11 @@ immédiatement suivis par la lettre $a$, puis n'importe quoi).
 $a$, $b$, $ab$, $ba$, $bb$, $bab$, $bba$, $baba$.  On ne demande pas
 de justifier les réponses.
 
+\begin{corrige}
+Les mots $\varepsilon$, $a$, $b$, $ab$ et $bb$ n'appartiennent pas
+à $L$ ; les mots $ba$, $bab$, $bba$ et $baba$ appartiennent à $L$.
+\end{corrige}
+
 \emph{Il est fortement conseillé, dans toutes les questions suivantes,
   d'utiliser les mots qui viennent d'être listés pour vérifier les
   automates successifs qu'on calculera.}  (Par exemple, pour un
@@ -155,22 +160,164 @@ l'automate ainsi obtenu.
 À défaut de donner l'automate de Glushkov ou de Thompson, donner un
 NFA reconnaissant $L$ pourra apporter une partie des points.)
 
+\begin{corrige}
+L'automate $\mathscr{A}_1$ trouvé est le suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$};
+\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$};
+\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$a$} (q4);
+\draw[->] (q3) -- node[auto,below]{$b$} (q5);
+\draw[->] (q4) to[loop above] node[auto]{$a$} (q4);
+\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5);
+\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4);
+\draw[->] (q5) to[loop below] node[auto]{$b$} (q5);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
 (2) Déterminiser l'automate $\mathscr{A}_1$.  On appellera
 $\mathscr{A}_2$ l'automate en question.  On rappelle qu'on attend ici
 un automate fini \emph{déterministe complet}.
 
+\begin{corrige}
+L'automate $\mathscr{A}_1$ est déjà déterministe, mais incomplet :
+pour le transformer en automate déterministe complet, on se contente
+de lui ajouter un puits pour obtenir l'automate $\mathscr{A}_2$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state,final,accepting below] {$3$};
+\node (q4) at (240bp,30bp) [draw,circle,state,final] {$4$};
+\node (q5) at (240bp,-30bp) [draw,circle,state,final] {$5$};
+\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q1) to[out=330,in=210] node[auto,below]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$a$} (q4);
+\draw[->] (q3) -- node[auto,below]{$b$} (q5);
+\draw[->] (q4) to[loop above] node[auto]{$a$} (q4);
+\draw[->] (q4) to[out=240,in=120] node[auto,swap]{$b$} (q5);
+\draw[->] (q5) to[out=60,in=300] node[auto,swap]{$a$} (q4);
+\draw[->] (q5) to[loop below] node[auto]{$b$} (q5);
+\draw[->] (q0) -- node[auto,swap]{$a$} (Sink);
+\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
 (3) Minimiser l'automate $\mathscr{A}_2$.  On appellera
 $\mathscr{A}_3$ l'automate minimal ainsi obtenu (automate canonique du
 langage $L$).
 
+\begin{corrige}
+L'automate $\mathscr{A}_2$ est déterministe complet sans état
+inaccessible.  On commence l'algorithme de minimisation en séparant
+les états finaux $\{3,4,5\}$ et non-finaux $\{0,1,2,\bot\}$.  On
+sépare ensuite ces derniers en deux classes, $\{1,2\}$ et $\{0,\bot\}$
+selon que la transition étiquetée $a$ conduit à un état final.  Enfin,
+la transition étiquetée $b$ sépare la classe $\{0,\bot\}$ en deux.
+Finalement, on aboutit aux classes suivantes : $\{0\}$, $\{1,2\}$,
+$\{3,4,5\}$ et $\{\bot\}$, et à l'automate minimal $\mathscr{A}_3$
+suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (q3) at (120bp,0bp) [draw,circle,state,final] {$3$};
+\node (Sink) at (0bp,-50bp) [draw,circle] {$\bot$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3);
+\draw[->] (q0) -- node[auto,swap]{$a$} (Sink);
+\draw[->] (Sink) to[loop left] node[auto]{$a,b$} (Sink);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
 (4) Déduire de $\mathscr{A}_3$ un automate fini déterministe complet
 $\mathscr{A}_4$ reconnaissant le langage $M := \Sigma^*\setminus L$
 complémentaire de $L$.
 
+\begin{corrige}
+Il suffit d'échanger les états finaux et non-finaux
+dans $\mathscr{A}_3$, ce qui donne l'automate $\mathscr{A}_4$
+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 (60bp,0bp) [draw,circle,state,final,accepting below] {$1$};
+\node (q3) at (120bp,0bp) [draw,circle,state] {$3$};
+\node (qZ) at (0bp,-50bp) [draw,circle,final] {$Z$};
+\draw[->] (q0) -- node[auto]{$b$} (q1);
+\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a,b$} (q3);
+\draw[->] (q0) -- node[auto,swap]{$a$} (qZ);
+\draw[->] (qZ) to[loop left] node[auto]{$a,b$} (qZ);
+\end{tikzpicture}
+\end{center}
+(On a renommé l'état $\bot$ en $Z$ vu que ce n'est plus un puits sur
+ce nouvel automate, en revanche $3$ en est un.  Ces nom sont, bien
+sûr, sans aucun impact sur le fonctionnement de l'automate.)
+\end{corrige}
+
 (5) En appliquant l'algorithme d'élimination des états, déduire
 de $\mathscr{A}_4$ une expression rationnelle $s$ dénotant le
 langage $M$ (c'est-à-dire vérifiée exactement par les mots qui ne
 vérifient pas $r$).
+\begin{corrige}
+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 :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {$1$};
+\node (qZ) at (0bp,-50bp) [draw,circle] {$Z$};
+\node (final) at (60bp,-50bp) [draw,circle,final] {$\infty$};
+\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[->] (q0) -- node[auto]{$\varepsilon$} (final);
+\draw[->] (q1) -- node[auto]{$\varepsilon$} (final);
+\draw[->] (qZ) -- node[auto,below]{$\varepsilon$} (final);
+\end{tikzpicture}
+\end{center}
+L'élimination de l'état $1$ conduit à remplacer la transition
+$0\to\infty$ étiquetée $\varepsilon$ par $\varepsilon | bb{*}$, et
+l'élimination de l'état $Z$ conduit à y ajouter $a(a|b){*}$.
+Finalement, on a affaire à un automate ayant les seuls états $0$
+(initial) et $\infty$ (final) avec la seule transition $0\to\infty$
+étiquetée par l'expression rationnelle $s$ recherchée :
+\[
+\varepsilon \,|\, bb{*} \,|\, a(a|b){*}
+\]
+qui dénote le langage $M$ complémentaire de $L$.  (Autrement dit : un
+mot qui \emph{n'est pas} un nombre $\geq 1$ de $b$ suivi d'un $a$
+suivi de n'importe quoi, c'est la même chose qu'un mot soit vide, soit
+formé uniquement d'un nombre $\geq 1$ de $b$, soit d'un $a$ suivi de
+n'importe quoi.)
+\end{corrige}
 
 
 %