path: root/controle-20220616.tex

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