From fd6bb02495c239ed1de3fa7f5ad11c04da36eaa6 Mon Sep 17 00:00:00 2001
From: "David A. Madore" <david+git@madore.org>
Date: Thu, 2 Jun 2022 13:28:50 +0200
Subject: Start writing an exam.

---
 controle-20220616.tex | 456 ++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 456 insertions(+)
 create mode 100644 controle-20220616.tex

(limited to 'controle-20220616.tex')

diff --git a/controle-20220616.tex b/controle-20220616.tex
new file mode 100644
index 0000000..cf36e07
--- /dev/null
+++ b/controle-20220616.tex
@@ -0,0 +1,456 @@
+%% This is a LaTeX document.  Hey, Emacs, -*- latex -*- , get it?
+\documentclass[12pt,a4paper]{article}
+\usepackage[francais]{babel}
+\usepackage[utf8]{inputenc}
+\usepackage[T1]{fontenc}
+%\usepackage{ucs}
+\usepackage{times}
+% A tribute to the worthy AMS:
+\usepackage{amsmath}
+\usepackage{amsfonts}
+\usepackage{amssymb}
+\usepackage{amsthm}
+%
+\usepackage{mathrsfs}
+\usepackage{wasysym}
+\usepackage{url}
+%
+\usepackage{graphics}
+\usepackage[usenames,dvipsnames]{xcolor}
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata,positioning}
+\usepackage{hyperref}
+%
+\theoremstyle{definition}
+\newtheorem{comcnt}{Tout}
+\newcommand\thingy{%
+\refstepcounter{comcnt}\smallskip\noindent\textbf{\thecomcnt.} }
+\newcommand\exercice{%
+\refstepcounter{comcnt}\bigskip\noindent\textbf{Exercice~\thecomcnt.}\par\nobreak}
+\renewcommand{\qedsymbol}{\smiley}
+%
+\DeclareUnicodeCharacter{00A0}{~}
+\DeclareUnicodeCharacter{03B5}{$\varepsilon$}
+%
+\DeclareMathSymbol{\tiret}{\mathord}{operators}{"7C}
+\DeclareMathSymbol{\traitdunion}{\mathord}{operators}{"2D}
+%
+%
+\DeclareFontFamily{U}{manual}{} 
+\DeclareFontShape{U}{manual}{m}{n}{ <->  manfnt }{}
+\newcommand{\manfntsymbol}[1]{%
+    {\fontencoding{U}\fontfamily{manual}\selectfont\symbol{#1}}}
+\newcommand{\dbend}{\manfntsymbol{127}}% Z-shaped
+\newcommand{\danger}{\noindent\hangindent\parindent\hangafter=-2%
+  \hbox to0pt{\hskip-\hangindent\dbend\hfill}}
+%
+\newcommand{\spaceout}{\hskip1emplus2emminus.5em}
+\newif\ifcorrige
+\corrigetrue
+\newenvironment{corrige}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Corrigé.}}\quad}}
+{{\hbox{}\nobreak\hfill\checkmark}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+\newenvironment{commentaire}%
+{\ifcorrige\relax\else\setbox0=\vbox\bgroup\fi%
+\smallbreak\noindent{\underbar{\textit{Commentaires.}}\quad}}
+{{\hbox{}\nobreak\hfill\maltese}%
+\ifcorrige\par\smallbreak\else\egroup\par\fi}
+%
+%
+% NOTE: compile dot files with
+% dot2tex --figonly -f tikz --tikzedgelabels --graphstyle=automaton file.dot  > file.tex
+\tikzstyle{automaton}=[>=stealth',initial text={},thick,every loop/.style={min distance=7mm,looseness=5}]
+\tikzstyle{state}=[]
+\tikzstyle{final}=[accepting by arrow]
+%
+%
+%
+\begin{document}
+\ifcorrige
+\title{INF105\\Contrôle de connaissances — Corrigé\\{\normalsize Théorie des langages}}
+\else
+\title{INF105\\Contrôle de connaissances\\{\normalsize Théorie des langages}}
+\fi
+\author{}
+\date{16 juin 2022}
+\maketitle
+
+\pretolerance=8000
+\tolerance=50000
+
+\vskip1truein\relax
+
+\noindent\textbf{Consignes.}
+
+Les exercices sont totalement indépendants.  Ils pourront être traités
+dans un ordre quelconque, mais on demande de faire apparaître de façon
+très visible dans les copies où commence chaque exercice.
+
+\medbreak
+
+L'usage de tous les documents (notes de cours manuscrites ou
+imprimées, feuilles d'exercices, livres) est autorisé.
+
+L'usage des appareils électroniques est interdit.
+
+\medbreak
+
+Durée : 1h30
+
+Barème \emph{indicatif} : \textcolor{red}{à remplir}.
+
+\ifcorrige
+Ce corrigé comporte \textcolor{red}{à remplir} pages (page de garde incluse).
+\else
+Cet énoncé comporte \textcolor{red}{à remplir} pages (page de garde incluse).
+\fi
+
+\vfill
+
+{\tiny\noindent
+\immediate\write18{sh ./vc > vcline.tex}
+Git: \input{vcline.tex}
+\immediate\write18{echo ' (stale)' >> vcline.tex}
+\par}
+
+\pagebreak
+
+
+%
+%
+%
+
+\exercice
+
+Dans cet exercice, on pose $\Sigma = \{a,b\}$.  On considère
+l'expression rationnelle $r := a{*}b{*}a{*}$, et soit $L := L(r)$ le
+langage qu'elle dénote.
+
+(0) Pour chacun des mots suivants, dire si oui ou non il appartient
+à $L$ (c'est-à-dire s'il vérifie $r$) : $\varepsilon$ (le mot vide),
+$a$, $b$, $ab$, $ba$, $aa$, $aba$, $bab$, $abab$.  On ne demande pas
+de justifier les réponses.
+
+\begin{corrige}
+Les mots $\varepsilon$, $a$, $b$, $ab$, $ba$, $aa$, $aba$
+appartiennent à $L$ ; les mots $bab$ et $baba$ n'appartiennent pas
+à $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
+automate censé reconnaître le langage $L$, on vérifiera qu'il accepte
+bien les mots qu'on a identifiés comme appartenant à $L$ et pas ceux
+qu'on a identifiés comme n'appartement pas à $L$.)  Les fautes qui
+auraient dû être détectées par cette vérification pourront être plus
+lourdement sanctionnées.
+
+(1) Traiter l'une \emph{ou} l'autre des questions suivantes :
+(i) construire l'automate de Glushkov $\mathscr{A}_1$ de $r$ ;
+(ii) construire l'automate de Thompson de $r$, puis éliminer les
+transitions spontanées (= $\varepsilon$-transitions) de ce dernier (on
+retirera les états devenus inutiles) : on appellera $\mathscr{A}_1$
+l'automate ainsi obtenu.
+
+(Dans les deux cas, on obtient le même automate fini $\mathscr{A}_1$,
+et il a $4$ états.  À 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,final,accepting above] {$0$};
+\node (q1) at (60bp,0bp) [draw,circle,state,final,accepting below] {$1$};
+\node (q2) at (120bp,0bp) [draw,circle,state,final,accepting below] {$2$};
+\node (q3) at (180bp,0bp) [draw,circle,state,final] {$3$};
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) to[loop above] node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a$} (q3);
+\draw[->] (q0) to[out=295,in=245] node[auto,below]{$b$} (q2);
+\draw[->] (q1) to[out=295,in=245] node[auto,below]{$a$} (q3);
+\draw[->] (q0) to[out=270,in=270] node[auto,below]{$a$} (q3);
+\end{tikzpicture}
+\end{center}
+(on remarquera notamment que tous ses états sont finaux).
+\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} ; pour information, il a
+$5$ états.
+
+\begin{corrige}
+L'automate $\mathscr{A}_2$ trouvé est le suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q0) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$\scriptstyle\{0\}$};
+\node (q1) at (30bp,52bp) [draw,circle,state,final,accepting right] {$\scriptstyle\{1,3\}$};
+\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$\scriptstyle\{2\}$};
+\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$\scriptstyle\{3\}$};
+\node (qF) at (180bp,0bp) [draw,circle,state] {$\varnothing$};
+\draw[->] (q0) -- node[auto]{$b$} (q2);
+\draw[->] (q0) -- node[auto]{$a$} (q1);
+\draw[->] (q1) to[loop above] node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) to[loop above] node[auto,near end]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (qF);
+\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF);
+\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$).  Pour information, cet automate a $4$ états : pour la
+commodité du correcteur, on les appellera $1,2,3,\bot$ dans l'ordre
+dans lequel ils sont parcourus lorsque l'automate consomme le
+mot $bab$.
+
+\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 $\{0\},\{1,3\},\{2\},\{3\}$ et l'état
+non-final $\varnothing$.  On sépare ensuite les premiers selon que la
+transition étiquetée $b$ conduit à un état non-final, ce qui
+sépare $\{3\}$ du reste, et enfin selon que la transition
+étiquetée $a$ conduit à cet état $\{3\}$, ce qui sépare $\{2\}$ du
+reste.  Finalement, on aboutit aux classes suivantes : $\{0\} \equiv
+\{1,3\}$, $\{2\}$, $\{3\}$ et $\varnothing$ (qu'on rebaptise
+$1,2,3,\bot$ respectivement), et à l'automate minimal $\mathscr{A}_3$
+suivant :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$};
+\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$2$};
+\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$3$};
+\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$};
+\draw[->] (q1) to[loop above] node[auto]{$a$} (q1);
+\draw[->] (q1) -- node[auto]{$b$} (q2);
+\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto]{$b$} (qF);
+\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(4) Donner de même l'automate minimal $\mathscr{A}_4$ du langage $L'
+:= L(r')$ dénoté par l'expression rationnelle $r' := b{*}a{*}b{*}$.
+Comme ce langage, et donc cet automate, est simplement obtenu en
+échangeant $a$ et $b$ par rapport à ce qui précède, on donnera
+directement l'automate sans passer par les questions intermédiaires.
+
+\begin{corrige}
+L'automate minimal $\mathscr{A}_4$ de $L'$ s'obtient simplement en
+échangeant $a$ et $b$ dans $\mathscr{A}_3$ :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$};
+\node (q2) at (60bp,0bp) [draw,circle,state,final,accepting below] {$2$};
+\node (q3) at (120bp,0bp) [draw,circle,state,final,accepting below] {$3$};
+\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$};
+\draw[->] (q1) to[loop above] node[auto]{$b$} (q1);
+\draw[->] (q1) -- node[auto]{$a$} (q2);
+\draw[->] (q2) to[loop above] node[auto]{$a$} (q2);
+\draw[->] (q2) -- node[auto]{$b$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$b$} (q3);
+\draw[->] (q3) -- node[auto]{$a$} (qF);
+\draw[->] (qF) to[loop above] node[auto]{$a,b$} (qF);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(5) En utilisant une construction de type « automate produit », donner
+un automate déterministe complet $\mathscr{A}_5$, ayant $4\times 4 =
+16$ états, qui reconnaît le langage $M := L \cap L'$ (constitué des
+mots vérifiant à la fois $r$ et $r'$).  On prendra garde pour la
+question suivante au fait que cet automate possède des états
+inaccessibles.
+
+\begin{corrige}
+En prenant le produit des automates
+$\mathscr{A}_3$ et $\mathscr{A}_4$, on aboutit à l'automate suivant
+(où on a noté $q,q'$ l'état correspondant au couple $(q,q')$ d'un état
+$q$ de $\mathscr{A}_3$ et $q'$ de $\mathscr{A}_4$ ; par exemple,
+$\delta((1,1),a) = (1,2)$ car $\delta_{\mathscr{A}_3}(1,a) = 1$ et
+$\delta_{\mathscr{A}_4}(1,a) = 2$) :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q11) at (0bp,0bp) [draw,circle,state,initial,accepting by double] {\footnotesize$1,1$};
+\node (q12) at (60bp,0bp) [draw,circle,state,accepting by double] {\footnotesize$1,2$};
+\node (q13) at (120bp,0bp) [draw,circle,state,accepting by double] {\footnotesize$1,3$};
+\node (q1F) at (180bp,0bp) [draw,circle,state] {\footnotesize$1,\bot$};
+\node (q21) at (0bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,1$};
+\node (q22) at (60bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,2$};
+\node (q23) at (120bp,-60bp) [draw,circle,state,accepting by double] {\footnotesize$2,3$};
+\node (q2F) at (180bp,-60bp) [draw,circle,state] {\footnotesize$2,\bot$};
+\node (q31) at (0bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,1$};
+\node (q32) at (60bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,2$};
+\node (q33) at (120bp,-120bp) [draw,circle,state,accepting by double] {\footnotesize$3,3$};
+\node (q3F) at (180bp,-120bp) [draw,circle,state] {\footnotesize$3,\bot$};
+\node (qF1) at (0bp,-180bp) [draw,circle,state] {\footnotesize$\bot,1$};
+\node (qF2) at (60bp,-180bp) [draw,circle,state] {\footnotesize$\bot,2$};
+\node (qF3) at (120bp,-180bp) [draw,circle,state] {\footnotesize$\bot,3$};
+\node (qFF) at (180bp,-180bp) [draw,circle,state] {\footnotesize$\bot,\bot$};
+\draw[->] (q11) -- node[auto]{$b$} (q21);
+\draw[->] (q11) -- node[auto]{$a$} (q12);
+\draw[->] (q12) -- node[auto]{$b$} (q23);
+\draw[->] (q12) to[loop above] node[auto]{$a$} (q12);
+\draw[->] (q13) -- node[auto]{$b$} (q23);
+\draw[->] (q13) -- node[auto]{$a$} (q1F);
+\draw[->] (q1F) -- node[auto]{$b$} (q2F);
+\draw[->] (q1F) to[loop right] node[auto]{$a$} (q1F);
+\draw[->] (q21) to[loop left] node[auto]{$b$} (q21);
+\draw[->] (q21) -- node[auto]{$a$} (q32);
+\draw[->] (q22) -- node[auto]{$b$} (q23);
+\draw[->] (q22) -- node[auto]{$a$} (q32);
+\draw[->] (q23) to[loop right] node[auto]{$b$} (q23);
+\draw[->] (q23) -- node[auto]{$a$} (q3F);
+\draw[->] (q2F) to[loop right] node[auto]{$b$} (q2F);
+\draw[->] (q2F) -- node[auto]{$a$} (q3F);
+\draw[->] (q31) -- node[auto]{$b$} (qF1);
+\draw[->] (q31) -- node[auto]{$a$} (q32);
+\draw[->] (q32) -- node[auto]{$b$} (qF3);
+\draw[->] (q32) to[loop below] node[auto]{$a$} (q32);
+\draw[->] (q33) -- node[auto]{$b$} (qF3);
+\draw[->] (q33) -- node[auto]{$a$} (q3F);
+\draw[->] (q3F) -- node[auto]{$b$} (qFF);
+\draw[->] (q3F) to[loop right] node[auto]{$a$} (q3F);
+\draw[->] (qF1) to[loop below] node[auto]{$b$} (qF1);
+\draw[->] (qF1) -- node[auto]{$a$} (qF2);
+\draw[->] (qF2) -- node[auto]{$b$} (qF3);
+\draw[->] (qF2) to[loop below] node[auto]{$a$} (qF2);
+\draw[->] (qF3) to[loop below] node[auto]{$b$} (qF3);
+\draw[->] (qF3) -- node[auto]{$a$} (qFF);
+\draw[->] (qFF) to[loop below] node[auto]{$a,b$} (qFF);
+\end{tikzpicture}
+\end{center}
+Pour plus de lisibilité, on a ici noté les états finaux en les
+entourant deux fois plutôt qu'avec une flèche sortante.
+\end{corrige}
+
+(6) Minimiser l'automate $\mathscr{A}_5$.  On appellera
+$\mathscr{A}_6$ l'automate minimal ainsi obtenu (automate canonique du
+langage $M = L \cap L'$).  Pour information, cet automate a $6$ états.
+
+\begin{corrige}
+On commence par ne conserver que les états accessibles depuis l'état
+initial, c'est-à-dire ceux étiquetés $(1,1)$, $(1,2)$, $(2,1)$,
+$(2,3)$, $(3,2)$, $(3,\bot)$, $(\bot,3)$ et $(\bot,\bot)$ dans la
+représentation ci-dessus, pour avoir un automate déterministe complet
+sans état inaccessible.  On applique ensuite l'algorithme de
+minimisation de manière semblable à la question (3) : les états
+non-finaux vont toujours rester groupés, et les états finaux sont
+séparés un par un.  Finalement, on aboutit à l'automate
+$\mathscr{A}_6$ suivant comme automate minimal du langage $M$ (on a
+rebaptisé les états ainsi : $(1,1)\rightsquigarrow 1$,
+$(2,1)\rightsquigarrow 2$, $(3,2)\rightsquigarrow 3$,
+$(1,2)\rightsquigarrow 2'$, $(2,3)\rightsquigarrow 3'$, et
+$(3,\bot)\equiv (\bot,3) \equiv (\bot,\bot) \rightsquigarrow \bot$) :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial,final,accepting below] {$1$};
+\node (q2a) at (60bp,42bp) [draw,circle,state,final,accepting below] {$2'$};
+\node (q3a) at (120bp,42bp) [draw,circle,state,final,accepting below] {$3'$};
+\node (q2) at (60bp,-42bp) [draw,circle,state,final,accepting below] {$2$};
+\node (q3) at (120bp,-42bp) [draw,circle,state,final,accepting below] {$3$};
+\node (qF) at (180bp,0bp) [draw,circle,state] {$\bot$};
+\draw[->] (q1) -- node[auto]{$a$} (q2a);
+\draw[->] (q1) -- node[auto,below]{$b$} (q2);
+\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a);
+\draw[->] (q2a) -- node[auto]{$b$} (q3a);
+\draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a);
+\draw[->] (q3a) -- node[auto]{$a$} (qF);
+\draw[->] (q2) to[loop above] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto,below]{$a$} (q3);
+\draw[->] (q3) to[loop above] node[auto]{$a$} (q3);
+\draw[->] (q3) -- node[auto,below]{$b$} (qF);
+\draw[->] (qF) to[loop right] node[auto]{$a,b$} (qF);
+\end{tikzpicture}
+\end{center}
+\vskip-\baselineskip\vskip-1ex\strut
+\end{corrige}
+
+(7) En appliquant l'algorithme d'élimination des états, déduire
+de $\mathscr{A}_6$ une expression rationnelle $s$ dénotant le
+langage $M$.  Pour obtenir une expression raisonnablement simple, on
+recommande d'éliminer les états en commençant par ceux qui sont à la
+distance la plus éloignée de l'état initial.
+
+\begin{corrige}
+On commence par effacer l'état puits (qui ne sert à rien) et par créer
+un unique état final sans transition qui en parte :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
+\node (q2a) at (60bp,42bp) [draw,circle,state] {$2'$};
+\node (q3a) at (120bp,42bp) [draw,circle,state] {$3'$};
+\node (q2) at (60bp,-42bp) [draw,circle,state] {$2$};
+\node (q3) at (120bp,-42bp) [draw,circle,state] {$3$};
+\node (qT) at (180bp,0bp) [draw,circle,state,final] {$\infty$};
+\draw[->] (q1) -- node[auto]{$a$} (q2a);
+\draw[->] (q1) -- node[auto,below]{$b$} (q2);
+\draw[->] (q1) -- node[auto]{$\varepsilon$} (qT);
+\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a);
+\draw[->] (q2a) -- node[auto]{$b$} (q3a);
+\draw[->] (q3a) to[loop above] node[auto]{$b$} (q3a);
+\draw[->] (q2a) -- node[auto]{$\varepsilon$} (qT);
+\draw[->] (q3a) -- node[auto]{$\varepsilon$} (qT);
+\draw[->] (q2) to[loop below] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto,below]{$a$} (q3);
+\draw[->] (q3) to[loop below] node[auto]{$a$} (q3);
+\draw[->] (q2) -- node[auto]{$\varepsilon$} (qT);
+\draw[->] (q3) -- node[auto,below]{$\varepsilon$} (qT);
+\end{tikzpicture}
+\end{center}
+
+On peut alors éliminer les états $3$ et $3'$ (il n'y a pas
+d'interaction entre eux) :
+\begin{center}
+\begin{tikzpicture}[>=latex,line join=bevel,automaton]
+\node (q1) at (0bp,0bp) [draw,circle,state,initial] {$1$};
+\node (q2a) at (60bp,42bp) [draw,circle,state] {$2'$};
+\node (q2) at (60bp,-42bp) [draw,circle,state] {$2$};
+\node (qT) at (120bp,0bp) [draw,circle,state,final] {$\infty$};
+\draw[->] (q1) -- node[auto]{$a$} (q2a);
+\draw[->] (q1) -- node[auto,below]{$b$} (q2);
+\draw[->] (q1) -- node[auto]{$\varepsilon$} (qT);
+\draw[->] (q2a) to[loop above] node[auto]{$a$} (q2a);
+\draw[->] (q2a) -- node[auto]{$\varepsilon|bb{*}$} (qT);
+\draw[->] (q2) to[loop below] node[auto]{$b$} (q2);
+\draw[->] (q2) -- node[auto,below,near end]{$\varepsilon|aa{*}$} (qT);
+\end{tikzpicture}
+\end{center}
+
+Et finalement, en éliminant les états $2$ et $2'$, on trouve
+l'expression rationnelle suivante qui dénote le langage $M$ :
+\[
+\varepsilon\,|\,aa{*}(\varepsilon|bb{*})\,|\,bb{*}(\varepsilon|aa{*})
+\]
+(il y a bien sûr d'autres écritures possibles ; par exemple, si on
+élimine d'abord $2$ et $2'$ puis $3$ et $3'$ on obtient :
+$\varepsilon\,|\,aa{*}\,|\,bb{*}\,|\,aa{*}bb{*}\,|\,bb{*}aa{*}$ ;
+l'expression rationnelle $\varepsilon\,|\,aa{*}b{*}\,|\,bb{*}a{*}$ est
+encore équivalente, mais elle ne s'obtient pas par la procédure
+d'élimination des états).
+\end{corrige}
+
+
+%
+%
+%
+\end{document}
-- 
cgit v1.2.3