First exercise for 2023 test.

1 files changed, 422 insertions, 37 deletions

diff --git a/controle-20230615.tex b/controle-20230615.tex
index 358cab2..cc97f35 100644
--- a/controle-20230615.tex
+++ b/controle-20230615.tex
@@ -282,55 +282,440 @@ $A_{\mathrm{z}}$\rule[-2ex]{0pt}{0pt}&
 \end{tabular}
 \end{center}
 
-On définit aussi les dix langages suivants où $w_0$ désigne le
+On définit aussi les douze langages suivants, où $w_0$ désigne le
 mot $ababb$ :
 \begin{itemize}
-\item $L_0$: le langage vide.
-\item $L_1$: le langage constitué du seul mot $w_0$.
-\item $L_2$: le langage constitué des mots qui sont un sous-mot de
+\item $L_0 = \varnothing$ : le langage vide.
+\item $L_1 = \{w_0\}$ : le langage constitué du seul mot $w_0$.
+\item $L_2$ : le langage constitué des mots qui sont un sous-mot de
   $w_0$.
-\item $L_3$: le langage constitué des mots qui ont $w_0$ comme
+\item $L_3$ : le langage constitué des mots qui ont $w_0$ comme
   sous-mot.
-\item $L_4$: le langage constitué des mots qui sont un facteur de
+\item $L_4$ : le langage constitué des mots qui sont un facteur de
   $w_0$.
-\item $L_5$: le langage constitué des mots qui ont $w_0$ comme
+\item $L_5$ : le langage constitué des mots qui ont $w_0$ comme
   facteur.
-\item $L_6$: le langage constitué des mots qui sont un préfixe de
+\item $L_6$ : le langage constitué des mots qui sont un préfixe de
   $w_0$.
-\item $L_7$: le langage constitué des mots qui ont $w_0$ comme
+\item $L_7$ : le langage constitué des mots qui ont $w_0$ comme
   préfixe.
-\item $L_8$: le langage constitué des mots qui sont un suffixe de
+\item $L_8$ : le langage constitué des mots qui sont un suffixe de
   $w_0$.
-\item $L_9$: le langage constitué des mots qui ont $w_0$ comme
+\item $L_9$ : le langage constitué des mots qui ont $w_0$ comme
   suffixe.
+\item $L_{10} = \{w_0^i : i\in\mathbb{N}\}$ : le langage constitué des
+  mots qui sont une répétition d'un nombre quelconque ($i$) de copies
+  de $w_0$ (par exemple, $ababbababb$).
+\item $L_{11} = \{b^i w_0 a^i : i\in\mathbb{N}\}$ : le langage
+  constitué des mots obtenus en précédant $w_0$ d'un nombre
+  quelconque ($i$) de copies de la lettre $b$ et en le suivant du même
+  nombre de copies de la lettre $a$ (par exemple, $bbababbaa$).
 \end{itemize}
 
-Pour chacun des huit automates $A \in
-\{A_{\mathrm{s}},A_{\mathrm{t}},A_{\mathrm{u}},A_{\mathrm{v}},A_{\mathrm{w}},A_{\mathrm{x}},A_{\mathrm{y}},A_{\mathrm{z}}\}$,
-on pose les questions suivantes :
-
-\textbf{(a)} Parmi les dix langages $L_0,\ldots,L_9$, lequel est le
-langage $L$ reconnu par l'automate $A$ ?  On ne demande pas de
-justifier la réponse.
-
-\textbf{(b)} Donner une expression rationnelle reconnaissant le
-langage $L$ en question.  On ne demande pas de justifier la réponse,
-et il n'est pas obligatoire d'appliquer un algorithme vu en cours ;
-par ailleurs, cette question-ci n'est pas posée pour
-l'automate $A_{\mathrm{z}}$.
-
-\textbf{(c)} De quel type d'automate vu en cours (DFA complet, DFA à
-spécification incomplète, NFA ou bien NFA à transitions spontanées)
-l'automate $A$ est-il ?  On donnera à chaque fois le type le plus
-particulier applicable.
-
-\textbf{(d)} Donner un DFA complet sans état inaccessible équivalent
-à $A$ (c'est-à-dire, reconnaissant le langage $L$).  On ne traitera
-que les cinq automates suivants :
-$A_{\mathrm{s}},A_{\mathrm{u}},A_{\mathrm{v}},A_{\mathrm{x}},A_{\mathrm{z}}$
-(c'est-à-dire que cette question-ci n'est pas posée pour
-$A_{\mathrm{t}},A_{\mathrm{w}},A_{\mathrm{y}}$) ; on appliquera les
-algorithmes vus en cours en les nommant.
+\textbf{(a)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}},
+A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}},
+A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire lequel ou
+lesquels parmi les douze langages $L_0,\ldots,L_{11}$ est celui
+reconnu par l'automate $A$.  On ne demande pas de justifier la
+réponse.
+
+\begin{corrige}
+L'automate $A_{\mathrm{s}}$ reconnaît le langage $L_1 = \{w_0\}$.
+
+L'automate $A_{\mathrm{t}}$ reconnaît le langage $L_9$ des mots ayant
+$w_0$ comme suffixe (car un chemin dans $A_{\mathrm{t}}$ finit par un
+chemin consommant $w_0$).
+
+L'automate $A_{\mathrm{u}}$ reconnaît le langage $L_7$ des mots ayant
+$w_0$ comme préfixe (car un chemin dans $A_{\mathrm{u}}$ commence
+par un chemin consommant $w_0$).
+
+L'automate $A_{\mathrm{v}}$ reconnaît le langage $L_5$ des mots ayant
+$w_0$ comme facteur (car un chemin dans $A_{\mathrm{u}}$ passe par un
+chemin consommant $w_0$).
+
+L'automate $A_{\mathrm{w}}$ reconnaît le langage $L_3$ des mots ayant
+$w_0$ comme sous-mot (car un chemin dans $A_{\mathrm{u}}$ consomme les
+lettres $a,b,a,b,b$ dans cet ordre, intercalées par un nombre
+quelconque de lettres quelconques).
+
+L'automate $A_{\mathrm{x}}$ reconnaît le langage $L_6$ des préfixes
+de $w_0$ (car un chemin dans $A_{\mathrm{x}}$ consomme le début
+de $w_0$).
+
+L'automate $A_{\mathrm{y}}$ reconnaît le langage $L_8$ des suffixes
+de $w_0$ (car un chemin dans $A_{\mathrm{y}}$ consomme la fin
+de $w_0$).
+
+L'automate $A_{\mathrm{z}}$ reconnaît le langage $L_4$ des facteurs
+de $w_0$ (car un chemin dans $A_{\mathrm{z}}$ consomme un intervalle
+de lettres consécutives de $w_0$).
+
+(Les justifications entre parenthèses n'étaient pas demandées.)
+\end{corrige}
+
+\textbf{(b)} Pour chacun des sept automates $A \in \{A_{\mathrm{s}},
+A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}},
+A_{\mathrm{x}}, A_{\mathrm{y}}\}$ (cette question-ci n'est pas posée
+pour $A_{\mathrm{z}}$), donner une expression rationnelle dénotant le
+langage $L$ reconnu par $A$.  On ne demande pas de justifier la
+réponse, et il n'est pas obligatoire d'appliquer un algorithme vu en
+cours.
+
+\begin{corrige}
+L'automate $A_{\mathrm{s}}$ reconnaît le langage dénoté par $ababb$.
+
+L'automate $A_{\mathrm{t}}$ reconnaît le langage dénoté
+par $(a|b){*}ababb$.
+
+L'automate $A_{\mathrm{u}}$ reconnaît le langage dénoté
+par $ababb(a|b){*}$.
+
+L'automate $A_{\mathrm{v}}$ reconnaît le langage dénoté
+par $(a|b){*}ababb(a|b){*}$.
+
+L'automate $A_{\mathrm{w}}$ reconnaît le langage dénoté
+par $(a|b){*}a(a|b){*}b(a|b){*}a(a|b){*}b(a|b){*}b(a|b){*}$.
+
+L'automate $A_{\mathrm{x}}$ reconnaît le langage dénoté
+par $\underline{\varepsilon}|a|ab|aba|abab|ababb$ (simple énumération
+de tous les préfixes de $w_0$) ou, si on préfère, par
+$\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|a(\underline{\varepsilon}|b(\underline{\varepsilon}|b))))$
+(obtenue en éliminant les états de $A_{\mathrm{x}}$ dans
+l'ordre $5,4,3,2,1,0$).
+
+L'automate $A_{\mathrm{y}}$ reconnaît le langage dénoté
+par $\underline{\varepsilon}|b|bb|abb|babb|ababb$ (simple énumération
+de tous les suffixes de $w_0$) ou, si on préfère, par
+$\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|(\underline{\varepsilon}|a)b)a)b)b$
+(obtenue en éliminant les états de $A_{\mathrm{y}}$ dans
+l'ordre $0,1,2,3,4,5$).
+\end{corrige}
+
+\textbf{(c)} Pour chacun des huit automates $A \in \{A_{\mathrm{s}},
+A_{\mathrm{t}}, A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{w}},
+A_{\mathrm{x}}, A_{\mathrm{y}}, A_{\mathrm{z}}\}$, dire de quel type
+d'automate vu en cours (DFA complet, DFA à spécification incomplète,
+NFA ou bien NFA à transitions spontanées) est l'automate $A$.  On
+donnera à chaque fois le type le plus particulier applicable.
+
+\begin{corrige}
+L'automate $A_{\mathrm{s}}$ est un DFA à spécification incomplète (ou
+DFAi).
+
+L'automate $A_{\mathrm{t}}$ est un NFA (à cause de la double
+transition étiquetée $a$ depuis l'état $0$).
+
+L'automate $A_{\mathrm{u}}$ est un DFA à spécification incomplète (ou
+DFAi).
+
+L'automate $A_{\mathrm{v}}$ est un NFA.
+
+L'automate $A_{\mathrm{w}}$ est un NFA.
+
+L'automate $A_{\mathrm{x}}$ est un DFA à spécification incomplète (ou
+DFAi).
+
+L'automate $A_{\mathrm{y}}$ est un NFA (à cause des multiples états
+initiaux).
+
+L'automate $A_{\mathrm{z}}$ est un NFA.
+\end{corrige}
+
+\textbf{(d)} Pour chacun des cinq automates $A \in \{A_{\mathrm{s}},
+A_{\mathrm{u}}, A_{\mathrm{v}}, A_{\mathrm{x}}, A_{\mathrm{z}}\}$
+(cette question-ci n'est pas posée pour $A_{\mathrm{t}},
+A_{\mathrm{w}}, A_{\mathrm{y}}$), donner un DFA complet sans état
+inaccessible qui soit équivalent à $A$ (c'est-à-dire, reconnaissant le
+langage $L$).  On appliquera un algorithme vu en cours en le nommant.
+
+{\footnotesize Conseil sur la présentation graphique : pour s'éviter
+  des maux de tête dans le placement des états (et en éviter aussi au
+  correcteur), il est conseillé de commencer par placer
+  horizontalement de gauche à droite les états successifs rencontrés
+  lors de la consommation du mot $w_0 = ababb$ par l'automate
+  construit, et d'ajouter ensuite les autres états éventuellement
+  nécessaires.\par}
+
+\begin{corrige}
+S'agissant de $A_{\mathrm{s}}$, comme c'est un DFAi, il s'agit
+simplement de lui ajouter un état « puits », noté $\bot$ ci-dessous,
+où aboutissent toutes les transitions manquantes :
+\begin{center}
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\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] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
+\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot);
+\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot);
+\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot);
+\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot);
+\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
+\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
+\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
+\end{tikzpicture}
+}
+\end{center}
+\vskip0ptplus20ex\relax
+La construction est analogue pour $A_{\mathrm{u}}$ :
+\begin{center}
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\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] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,final] {$5$};
+\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
+\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot);
+\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot);
+\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot);
+\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot);
+\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
+\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
+\end{tikzpicture}
+}
+\end{center}
+\vskip0ptplus20ex\relax S'agissant de $A_{\mathrm{v}}$, on a affaire à
+un « vrai » non-déterminisme et on applique donc l'algorithme de
+déterminisation vu en cours, qui donne (en omettant les accolades dans
+le nommage des états) :
+\begin{center}
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial] {\small $0$};
+\node (q1) at (60bp,0bp) [draw,circle,state] {\small $0,1$};
+\node (q2) at (120bp,0bp) [draw,circle,state] {\small $0,2$};
+\node (q3) at (180bp,0bp) [draw,circle,state] {\small $0,1,3$};
+\node (q4) at (240bp,0bp) [draw,circle,state] {\small $0,2,4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,final] {\small $0,5$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (q0) to[loop below] node[auto]{$b$} (q0);
+\draw[->] (q1) to[loop below] node[auto]{$a$} (q1);
+\draw[->] (q2) to[out=120,in=60] node[auto,swap]{$b$} (q0);
+\draw[->] (q3) to[out=120,in=60] node[auto,swap]{$a$} (q1);
+\draw[->] (q4) to[out=120,in=60] node[auto,swap]{$a$} (q3);
+\draw[->] (q5) to[loop above] node[auto]{$a,b$} (q5);
+\end{tikzpicture}
+}
+\end{center}
+\vskip0ptplus20ex\relax
+La construction pour $A_{\mathrm{x}}$ est exactement comme pour
+$A_{\mathrm{s}}$ sauf que les états $0$ à $5$ sont tous marqués
+finaux :
+\begin{center}
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(q0.base)]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$};
+\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\bot$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (q0) to[out=270,in=240] node[auto]{$b$} (qbot);
+\draw[->] (q1) to[out=270,in=210] node[auto]{$a$} (qbot);
+\draw[->] (q2) to[out=270,in=180] node[auto]{$b$} (qbot);
+\draw[->] (q3) to[out=270,in=150] node[auto]{$a$} (qbot);
+\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
+\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
+\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
+\end{tikzpicture}
+}
+\end{center}
+\vskip0ptplus20ex\relax
+S'agissant de $A_{\mathrm{z}}$, on a de nouveau affaire à un « vrai »
+non-déterminisme et on applique donc l'algorithme de déterminisation
+vu en cours, qui donne (en omettant les accolades dans le nommage des
+états) :
+\begin{center}
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)]
+\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$};
+\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$};
+\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$2,4$};
+\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$};
+\node (q245) at (120bp,-120bp) [draw,circle,state,accepting below] {\small $2,4,5$};
+\node (qbot) at (300bp,-90bp) [draw,circle,state] {$\varnothing$};
+\draw[->] (qI) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (qI) to[out=270,in=150] node[auto,swap]{$b$} (q245);
+\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot);
+\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5);
+\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot);
+\draw[->] (q4) to[out=270,in=120] node[auto,near start]{$a$} (qbot);
+\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
+\draw[->] (q245) to[out=60,in=240] node[auto]{$a$} (q3);
+\draw[->] (q245) to[out=30,in=240] node[auto,swap,very near end]{$b$} (q5);
+\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
+\end{tikzpicture}
+}
+\end{center}
+où on a noté $I$ au lieu de $\{0,1,2,3,4,5\}$.
+\end{corrige}
+
+\textbf{(e)} Pour $A = A_{\mathrm{z}}$ (et seulement celui-ci),
+minimiser le DFA trouvé à la question (d).
+
+\begin{corrige}
+On a affaire à un DFA complet sans état inaccessible : on va le
+minimiser avec l'algorithme de Moore.
+
+Dans une première étape, on fait deux classes d'état : celle des états
+finaux, c'est-à-dire $I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$
+et celle des états non-finaux, c'est-à-dire le seul
+état $\varnothing$.
+
+Séparons maintenant les états selon la cible de la transition
+étiquetée par $a$ : la classe formée de
+$I,\{1,3\},\{2,4\},\{2,4,5\},\{3\},\{4\},\{5\}$ se scinde en deux :
+$I,\{2,4\},\{2,4,5\}$ d'une part, où elle mène à un état final, et
+$\{1,3\},\{3\},\{4\},\{5\}$ d'autre part, où elle mène à un état
+non-final.  La cible de la transition étiquetée par $b$, pour sa part,
+sépare $\{5\}$ de tous les autres états (le seul où elle mène à un
+état non-final).  À ce stade, on a quatre classes : la classe formée
+de $I,\{2,4\},\{2,4,5\}$, celle de $\{1,3\},\{3\},\{4\}$, et deux
+classes singleton, $\{5\}$ et $\varnothing$.
+
+À l'étape suivante, la cible de la transition étiquetée par $a$ ne
+sépare rien (les états de la première classe mènent à la seconde et
+les états de la seconde mènent au puits).  La cible de la transition
+étiquetée par $b$, en revanche, sépare la classe formée de
+$I,\{2,4\},\{2,4,5\}$ en $I$ d'une part (qui mène à cette même classe)
+et $\{2,4\},\{2,4,5\}$ de l'autre (qui mène à $\{5\}$) ; et elle
+sépare la classe formée de $\{1,3\},\{3\},\{4\}$ en trois (puisque les
+cibles sont dans trois classes distinctes).  À ce stade, les seuls
+états qui n'ont pas été séparés sont $\{2,4\}$ et $\{2,4,5\}$.  Or
+comme ils ont exactement les mêmes cibles de transitions étiquetées
+par $a$ et $b$, ils ne sont pas séparés, donc l'algorithme s'applique
+ici : il fusionne exactement deux états, à savoir
+$\{2,4\}$ et $\{2,4,5\}$, en un seul, que nous noterons $B$ :
+\begin{center}
+\scalebox{0.85}{%
+\begin{tikzpicture}[>=latex,line join=bevel,automaton,baseline=(qI.base)]
+\node (qI) at (0bp,0bp) [draw,circle,state,initial,accepting above] {$I$};
+\node (q1) at (60bp,0bp) [draw,circle,state,accepting above] {$1,3$};
+\node (q2) at (120bp,0bp) [draw,circle,state,accepting above] {$B$};
+\node (q3) at (180bp,0bp) [draw,circle,state,accepting above] {$3$};
+\node (q4) at (240bp,0bp) [draw,circle,state,accepting above] {$4$};
+\node (q5) at (300bp,0bp) [draw,circle,state,accepting above] {$5$};
+\node (qbot) at (300bp,-60bp) [draw,circle,state] {$\varnothing$};
+\draw[->] (qI) -- node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (q4);
+\draw[->] (q4) -- node[auto]{$b$} (q5);
+\draw[->] (qI) to[out=60,in=120] node[auto]{$b$} (q2);
+\draw[->] (q1) to[out=270,in=180] node[auto,near start]{$a$} (qbot);
+\draw[->] (q2) to[out=60,in=120] node[auto]{$b$} (q5);
+\draw[->] (q3) to[out=270,in=150] node[auto,near start]{$a$} (qbot);
+\draw[->] (q4) to[out=270,in=120] node[auto]{$a$} (qbot);
+\draw[->] (q5) to[out=270,in=90] node[auto]{$a,b$} (qbot);
+\draw[->] (qbot) to[loop right] node[auto]{$a,b$} (qbot);
+\end{tikzpicture}
+}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+\textbf{(f)} Parmi les douze langages $L_0,\ldots,L_{11}$, lesquels
+sont rationnels ?  Lesquels sont algébriques ?  Lesquels sont
+décidables ?  Lesquels sont semi-décidables ?  On justifiera la
+réponse à chaque fois (par exemple en donnant une expression
+rationnelle, un automate, une grammaire hors-contexte, un algorithme,
+ou n'importe quel autre type d'argument applicable permettant de
+justifier la conclusion).
+
+\begin{corrige}
+Les langages $L_1,L_3,L_4,L_5,L_6,L_7,L_8,L_9$ sont rationnels car ils
+sont reconnaissables : on a vu que les automates $A_{\mathrm{s}},
+A_{\mathrm{w}}, A_{\mathrm{z}}, A_{\mathrm{v}}, A_{\mathrm{x}},
+A_{\mathrm{u}}, A_{\mathrm{y}}, A_{\mathrm{t}}$ respectivement les
+reconnaissent.  Il reste donc à traiter le cas de
+$L_0,L_2,L_{10},L_{11}$.
+
+Les langages $L_0$ et $L_2$ sont rationnels car ils sont finis (on
+peut donner des expressions rationnelles pour les deux, à savoir
+$\bot$ pour $L_0$ et, en énumérant systématiquement tous les
+sous-mots, $\varepsilon | b | bb | a | ab | abb | bbb | ba | bab |
+babb | aa | aab | aabb | abbb | aba | abab | ababb$ pour $L_2$, mais
+ce n'est pas très intéressant et ce n'était pas demandé).
+
+Le langage $L_{10} = \{w_0^i : i\in\mathbb{N}\} = L_1^*$ est rationnel
+car il est l'étoile de Kleene d'un langage rationnel (si on préfère,
+il est dénoté par l'expression rationnelle $(ababb){*}$).
+
+Tous les langages $L_0$ à $L_{10}$ sont donc rationnels, et, en
+particulier, algébriques, décidables et semi-décidables.
+
+Reste à évoquer le cas du langage $L_{11} = \{b^i w_0 a^i :
+i\in\mathbb{N}\}$.  Montrons qu'il n'est pas rationnel, et montrons
+qu'il est algébrique.
+
+Il n'est pas rationnel par le lemme de pompage.  En effet, supposons
+par l'absurde que $\{b^i w_0 a^i : i\in\mathbb{N}\}$ soit rationnel,
+et soit $k$ tel que donné par le lemme de pompage.  Considérons le mot
+$t := b^k ababb a^k \in L_{11}$.  D'après la propriété de $k$, il
+existe une factorisation $t = uvw$ vérifiant les propriétés garanties
+par le lemme de pompage.  Le fait que $|uv|\leq k$, comme le préfixe
+de longueur $k$ de $t$ est formé uniquement de la lettre $b$, assure
+que $u = b^{\ell_1}$ et $v = b^{\ell_2}$ pour certains $\ell_1,\ell_2$
+avec, de plus, $\ell_2 > 0$ (car $v\neq\varepsilon$) et
+$\ell_1+\ell_2\leq k$.  On a alors $w = b^{k-\ell_1-\ell_2} ababb
+a^k$, et $uv^iw = b^{k+(i-1)\ell_2} ababb a^k$.  Comme les mots de
+$L_{11}$ ont la propriété nécessaire que leur nombre initial de $b$
+(i.e., la longueur de leur plus long préfixe formé uniquement de la
+lettre $b$) est égale à leur nombre final de $a$ (i.e., la longueur de
+leur plus long suffixe formé uniquement de la lettre $a$), on devrait
+avoir $k+(i-1)\ell_2 = k$, ce qui est une contradiction dès que $i\neq
+1$.
+
+En revanche, le langage $L_{11}$ est algébrique, car il est engendré
+par la grammaire suivante d'axiome $S$ :
+\[
+S \rightarrow ababb \;|\; bSa
+\]
+Étant algébrique, le langage $L_{11}$ est décidable et semi-décidable.
+(Au demeurant, il est facile de donner un algorithme qui décide si un
+mot appartient à $L_{11}$ : on vérifie que son nombre initial de $b$
+est égal à son nombre final de $a$ et, une fois ce fait vérifié, on
+vérifie qu'une fois retiré le préfixe et le suffixe en question il
+reste exactement le mot $ababb$.)
+
+Pour résumer, tous les langages dont on a parlé sont algébriques,
+décidables et semi-décidables, et tous sauf $L_{11}$ sont rationnels.
+\end{corrige}