<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">


Des automates diffÃ©rents peuvent Ãªtre associÃ©s au mÃªme langage.\\

L'optimisation des programmes d'analyse syntaxique (dont certains sont des rÃ©alisations concrÃ¨tes d'automates finis) rend nÃ©cessaire la construction d'un automate minimal (en nombre d'Ã©tats) qui reconnaissent un langage donnÃ©.\\

On se limitera dans ce chapitre Ã&nbsp; la simplification d'un automate de Moore (puisque la mÃ©thode de construction par sous-ensemble permet de se ramener d'un AFND Ã&nbsp; un AFD).

\section{Congruences d'automates}

Soit $(E,I,t)$ un AFD et $\mathcal{R}$ une relation d'Ã©quivalence sur $E$.

\subsection{Quelques rappels}

On rappelle que $\mathcal{R}$ est une relation binaire sur l'ensemble $E$ des Ã©tats, qui a en plus les propriÃ©tÃ©s suivantes...
\begin{description}
\item[- rÃ©flÃ©xivitÃ©.] Pour tout Ã©tat $e \in E, ~ e \mathcal{R} e$,
\item[- symÃ©trie.] Pour tout couple d'Ã©tats $(e_1, e_2) \in E^2$ : si $e_1 \mathcal{R} e_2$, alors $e_2 \mathcal{R} e_1$,
\item[- transitivitÃ©.] Pour tout triplet d'Ã©tats $(e_1, e_2, e_3) \in E^3$ : si $e_1 \mathcal{R} e_2$ et $e_2 \mathcal{R} e_3$, alors $e_1 \mathcal{R} e_3$.
\end{description}

\medskip


\begin{Exo}
On considÃ¨re l'automate :

\unitlength = 0.9mm 
\begin{center}
\begin{picture}(143,75)(-50,-75)
\put(0,-75){}
\node[NLangle=0.0,Nmarks=i](n0)(16.0,-20.0){$e_0$}

\node[NLangle=0.0,iangle=128.23](n1)(44.0,-20.0){$e_1$}

\node[NLangle=0.0](n2)(16.0,-44.0){$e_2$}

\node[NLangle=0.0,Nmarks=r](n3)(44.0,-44.0){$e_3$}

\drawloop[ELdist=1.7,loopangle=37.45](n1){1}

\drawloop[ELdist=2.2,loopangle=225.0](n2){0}

\drawedge[ELdist=2.8](n0,n1){0}

\drawedge[ELdist=1.5](n1,n3){0}

\drawedge[ELside=r,ELdist=2.7](n2,n3){1}

\drawedge[ELside=r,ELdist=3.4](n0,n2){0,1}

\drawedge[ELside=r,ELdist=2.1](n0,n3){1}
\end{picture}
\end{center}
\noindent et la relation binaire $e_i \mathcal{R} e_j$ si et seulement si $i$ et $j$ ont la mÃªme paritÃ©.

Montrez que $\mathcal{R}$ est bien une relation d'Ã©quivalence sur $E$.
\end{Exo}


On rappelle encore que  $t : E \times I \rightarrow E$ est la fonction de transition. Par la suite, par souci de concision, on notera $t_{x}(e)$  pour $t(e,x)$.

\subsection{DÃ©finition}

\begin{Def}[Congruence d'automates]
On dit que $\mathcal{R}$ est une \emph{congruence d'automates}\index{congruence d'automates} si et seulement si
$$\forall (r,s) \in E^2, \forall x \in I, (r \mathcal{R} s) \Longrightarrow (t_x(r) \mathcal{R} t_x(s))$$ 
C'est-Ã&nbsp;-dire si toute paire d'Ã©tats Ã©quivalents modulo $\mathcal{R}$ est transformÃ©e par toute entrÃ©e en une paire d'Ã©tats Ã©quivalents modulo $\mathcal{R}$.
\end{Def}


\begin{Exo}
La relation d'Ã©quivalence $\mathcal{R}$ de l'exercice prÃ©cÃ©dent est-elle une congruence d'automates ?
\end{Exo}

\subsection{Ensemble quotient}

Soit $\mathcal{R}$ une congruence d'automates sur l'AFD $(E,I,t)$.

\begin{Notation}
On note $\tilde{E}$, l'ensemble quotient $E/\mathcal{R}$.\\
\end{Notation}



\begin{Exo}
 ReprÃ©senter le graphe de l'automate $M$ dont la table de transition des Ã©tats est
$$\begin{array}{|c|cc|}
   \hline
 t &amp; a &amp; b \\
 \hline
e_0 &amp; e_0 &amp; e_4\\
e_1 &amp; e_1 &amp; e_0 \\
e_2 &amp; e_2 &amp; e_4 \\
e_3 &amp; e_5 &amp; e_2 \\
e_4 &amp; e_4 &amp; e_3 \\
e_5 &amp; e_3 &amp; e_2 \\
\hline
  \end{array}
$$

Soit $\mathcal{R}$ la relation d'Ã©quivalence pour laquelle $E/ \mathcal{R} = \{ \{ e_0, e_2 \}, \{ e_1, e_3, e_5 \}, \{ e_4 \} \}.$

\begin{enumerate}
\item Donner la table de transition d'Ã©tats de l'automate-quotient.
\item ReprÃ©senter son graphe
\end{enumerate}
\end{Exo}


\noindent RÃ©ponses : 

$$\begin{array}{|c|c|c|}
\hline
E &amp; a &amp; b\\
\hline
A = \{e_0, e_2\} &amp; \{e_0, e_2\} &amp; \{e_4\} \\
B = \{e_1, e_3, e_5 \}  &amp; \{e_1, e_3, e_5 \} &amp;  \{e_0, e_2\}\\
C = \{e_4\} &amp; \{e_4\} &amp; \{e_1, e_3, e_5 \} \\
\hline
  \end{array}
$$

\begin{center}
\unitlength=1mm
\begin{picture}(74,83)(0,-83)
\put(0,-83){}
\node[NLangle=0.0](n7)(24.0,-36.0){C}

\node[NLangle=0.0](n8)(52.0,-16.0){A}

\node[NLangle=0.0](n9)(52.0,-56.0){B}

\drawedge[ELdist=2.0](n8,n7){b}

\drawedge[ELdist=2.0](n7,n9){b}

\drawedge(n9,n8){b}

\drawloop[ELdist=1.7,loopangle=53.62](n8){a}

\drawloop[ELdist=1.7,loopangle=-60.55](n9){a}

\drawloop[ELdist=1.7,loopangle=176.01](n7){a}
\end{picture}
\end{center}

\begin{Exo}
 Soit $M$ l'automate fini dont la table de transition des Ã©tats est

$$\begin{array}{|c|cc|}
   \hline
 t &amp; 0 &amp; 1 \\
 \hline 
1 &amp; 1 &amp; 4 \\
2 &amp; 3 &amp; 5 \\
3 &amp; 2 &amp; 5 \\
4 &amp; 4 &amp; 1 \\
5 &amp; 3 &amp; 4 \\
\hline
  \end{array}
$$

Soit $\mathcal{R}$ la relation d'Ã©quivalence sur $E = \{1,2,3,4,5\}$ telle que $1 \mathcal{R} 4$ et $3 \mathcal{R} 2$.
\begin{enumerate}
\item Que vaut $E/\mathcal{R}$?
\item Montrer que $\mathcal{R}$ est une congruence d'automates.
\item Donner la table de transition des Ã©tats de l'automate-quotient.
\item ReprÃ©senter son graphe.
\end{enumerate}
\end{Exo}



\begin{Exo}
 Soit $M$ l'automate fini dont le graphe est reprÃ©sentÃ© par la figure\\

\begin{center}
\unitlength = 1mm 
 \begin{picture}(103,62)(0,-62)
\put(0,-62){}
\node[NLangle=0.0](n16)(16.0,-16.0){0}

\node[NLangle=0.0](n17)(40.0,-16.0){1}

\node[NLangle=0.0](n18)(40.0,-40.0){3}

\node[NLangle=0.0](n19)(64.0,-16.0){5}

\node[NLangle=0.0](n20)(64.0,-40.0){4}

\drawedge[ELside=r,ELdist=2.2](n17,n19){1}

\drawedge[ELside=r,ELdist=2.8,syo=1.0,eyo=1.0](n19,n17){ 1}

\node[NLangle=0.0](n22)(88.0,-16.0){2}

\drawedge[ELdist=2.1](n20,n19){1}

\drawedge[ELdist=2.1](n19,n22){O}

\drawedge[ELdist=2.1](n22,n20){1}

\drawedge[ELdist=2.1](n17,n18){0}

\drawedge[ELdist=2.1](n18,n16){1}

\drawedge[ELdist=2.1](n16,n17){1}

\drawloop[ELside=r,ELdist=2.1](n22){0}

\drawloop[ELside=r,ELdist=2.1](n16){0}

\drawloop[ELside=r,ELdist=2.1,loopangle=-87.44](n18){0}

\drawloop[ELside=r,ELdist=2.1,loopangle=-90.0](n20){0}



\end{picture}
\end{center}

Le tableau ci-dessous figure une relation binaire $\mathcal{R}$ dans l'ensemble des Ã©tats $E = \{ 0,1,2,3,4,5 \}$ :

$$\begin{array}{|c|cccccc|}
   \hline
  &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 \\
\hline
0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \\
1 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 \\
2 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 \\
3 &amp; 0 &amp; 0 &amp; 1 &amp; 1 &amp; 0 &amp; 0 \\
4 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 0 \\
5 &amp; 0 &amp; 1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 \\
\hline
  \end{array}
$$

Un chiffre 1 Ã&nbsp; l'intersection de la ligne $i$ et de la colonne $j$ signifie que $i \mathcal{R} j$, et un chiffre 0 que ces deux Ã©lÃ©ments ne sont pas en relation.
\begin{enumerate}
 \item Montrer que $\mathcal{R}$ est une relation d'Ã©quivalence sur $E$.
 \item Montrer que $\mathcal{R}$ est une congruence d'automates.
\item ReprÃ©senter le graphe de l'automate-quotient $M/\mathcal{R}$.
\end{enumerate}
\end{Exo}

\noindent RÃ©ponses :

$$\begin{array}{c|c|c}
E &amp; 0 &amp; 1 \\
\hline
A = \{0, 4 \} &amp; \{0, 4 \} &amp; \{1, 5\} \\
B = \{1, 5\} &amp; \{3, 2\} &amp; \{1, 5\} \\
C = \{3, 2\} &amp; \{3, 2\} &amp; \{0, 4 \}\\
  \end{array}
$$

\begin{center}
 \unitlength=1mm

\begin{picture}(74,83)(0,-83)
\put(0,-83){}
\node[NLangle=0.0](n7)(24.0,-36.0){C}

\node[NLangle=0.0](n8)(52.0,-16.0){A}

\node[NLangle=0.0](n9)(52.0,-56.0){B}

\drawedge[ELdist=2.0](n7,n8){1}

\drawedge[ELdist=2.0](n9,n7){0}

\drawedge(n8,n9){1}

\drawloop[ELdist=1.7,loopangle=53.62](n8){0}

\drawloop[ELdist=1.7,loopangle=-60.55](n9){1}

\drawloop[ELdist=1.7,loopangle=176.01](n7){0}
\end{picture}
\end{center}

\begin{Rem}
On peut dÃ©finir une application $\tilde{t}_x : \tilde{E} \rightarrow \tilde{E}$ par $\tilde{t}_x (\dot{e}) = \dot{[t_x(e)]}$, puis une application $\tilde{t} : \tilde{E} \times I \rightarrow \tilde{E}$ par $(\dot{e},i) \longmapsto \tilde{t}_x(\dot{e})$.
\end{Rem}

\section{\'Equivalence de NÃ©rode}

\subsection{L'Ã©quivalence}

Soit $M = (E,I,t,e_0,A)$ un automate de Moore, deux Ã©tats $q$ et $s$ de $E$, et $w \in I^*$ un mot d'entrÃ©e.

\begin{Def}[w-compatibles]
 $q$ est $s$ sont \emph{$w$-compatible}\index{w-compatible} si et seulement si $$t_w(q) \in A \Longleftrightarrow t_w(s) \in A$$
\end{Def}

Cette dÃ©finition permet de dÃ©finir une relation $\sim$ dans $E$ par

$$(q \sim s) \Longleftrightarrow \left(\forall w \in I^*, q \textrm{ et } s \textrm{ sont } w \textrm{-compatibles} \right)$$

\begin{Def}[\'Equivalence de NÃ©rode]
Cette relation est manifestement une relation d'Ã©quivalence, elle est appelÃ©e \emph{\'equivalence de N\'erode}\index{Ã©quivalence!de NÃ©rode} associÃ©e Ã&nbsp; $M$.
\end{Def}


On dÃ©montre facilement que cette Ã©quivalence est une congruence d'automates. Tout automate de Moore peut donc Ãªtre remplacÃ© par son quotient par l'Ã©quivalence de NÃ©rode.

Dans ce quotient, le nombre d'Ã©tats est Ã©videmment plus petit, l'automate obtenu est donc plus \og simple\fg{}.






\subsection{L'algorithme}

\subsubsection{La thÃ©orie}

Pour obtenir l'Ã©quivalence de NÃ©rode associÃ©e Ã&nbsp; un automate, on dispose de l'algorithme suivant...\\\\

Soit $M=\{E,I,t,e_0,A\}$ un automate de Moore.

On dÃ©finit, pour tout $k \in \mathbb{N}$, une relation $\mathcal{R}_k$ sur E en posant

$$[ q \mathcal{R}_k s ] \Longleftrightarrow \left[ (\forall w \in I^*), (l(w) \leqslant k \Longrightarrow q \text{ et } s \text{ sont } w\text{-compatibles}) \right]$$

Donc $q$ et $s$ sont en relation par $\mathcal{R}_k$ lorsqu'ils sont $w$-compatibles, pour tout mot $w$ de longueur infÃ©rieure ou Ã©gale Ã&nbsp; $k$.\\

Cette relation est clairement une relation d'Ã©quivalence, et $\mathcal{R}_{k+1}$ est plus fine que $\mathcal{R}_k$. L'Ã©quivalence de NÃ©rode est l'intersection de ces relations $\mathcal{R}_k$, pour toutes les valeurs de $k$ entier.

\subsubsection{La pratique}

Cet algorithme n'est pas utilisable dans la pratique. On fait plutÃ´t...

\begin{enumerate}
 \item Prendre comme partition de dÃ©part $P_0 = \{A, E \setminus A \}$.
 \item Si $P_k=\{E_1, \hdots, E_n \} $ est la partition correspondant Ã&nbsp; la relation $\mathcal{R}_k$, morceler Ã©ventuellement chaque classe $E_i$ en sous-classes $E_{i1}, E_{i2}, \hdots, E_{ip}$ de maniÃ¨re que deux Ã©tats $q$ et $s$ appartiennent Ã&nbsp; la mÃªme sous-classe si, pour toute entrÃ©e $x$, les Ã©tats $t_x(q)$ et $t_x(s)$ appartiennent Ã&nbsp; la mÃªme classe $E_j$ (pouvant dÃ©pendre de $x$).

L'ensemble des sous-classes obtenues constitue la partition correspondant Ã&nbsp; la relation $\mathcal{R}_{k+1}$
\item RÃ©pÃ©ter l'Ã©tape prÃ©cÃ©dente jusqu'Ã&nbsp; ce que $P_{k+1}=P_k$. La relation $\mathcal{R}_k$ est alors l'Ã©quivalence de NÃ©rode associÃ©e Ã&nbsp; M.
\end{enumerate}

\begin{Rem}
L'Ã©tape (3) est nÃ©cessairement atteinte, puisque les relations $\mathcal{R}_k$ sont de plus en plus fines.

Au pire, $P = \{ \{q \} \|q \in E \}$, la relation est l'Ã©galitÃ© : ceci signifie que l'automate n'est pas simplifiable.
\end{Rem}


\begin{Ex}
 Un automate de Moore et l'automate simplifiÃ©.
\scriptsize
\begin{center}
\unitlength = 0.8mm 
\begin{picture}(174,77)(0,-77)
\put(0,-77){}
\node[NLangle=0.0,Nmarks=i](n24)(12.0,-12.0){1}

\node[NLangle=0.0](n25)(40.0,-12.0){2}

\node[NLangle=0.0,Nmarks=r](n26)(68.0,-12.0){3}

\node[NLangle=0.0,Nmarks=r](n27)(12.0,-36.0){4}

\node[NLangle=0.0](n28)(68.0,-36.0){7}

\node[NLangle=0.0,Nmarks=r](n29)(40.0,-60.0){5}

\node[NLangle=0.0](n30)(68.0,-60.0){6}

\drawedge[ELdist=2.0](n24,n25){a}

\drawedge[ELside=r,ELdist=2.0](n24,n27){b}

\drawedge[ELdist=2.0](n27,n28){b}

\drawedge[ELside=r,ELdist=2.0](n25,n28){b}

\drawedge[ELside=r,ELdist=2.0](n26,n28){a}

\drawedge[ELdist=2.0](n29,n28){a}

\drawedge[ELdist=2.0](n30,n28){b}

\drawedge[ELdist=2.0](n27,n29){a}

\drawedge[ELside=r,ELdist=3.1,syo=1.0,eyo=1.0](n26,n25){ b}

\drawedge[ELside=r,ELdist=2.0](n25,n26){a}

\drawedge[ELdist=3.0,syo=1.0,eyo=1.0](n29,n30){ b}

\drawedge[ELdist=2.0](n30,n29){a}

\drawloop[ELdist=2.5,loopangle=1.1](n28){a,b}

\node[NLangle=0.0,Nmarks=i](n31)(96.0,-20.0){1}

\node[NLangle=0.0,Nmarks=r](n32)(96.0,-52.0){4}

\node[NLangle=0.0,Nmarks=r](n33)(128.0,-52.0){3,5}

\node[NLangle=0.0](n34)(128.0,-20.0){2,6}

\node[NLangle=0.0](n35)(152.0,-36.0){7}

\drawloop[ELdist=2.0,loopangle=0.0](n35){ a,b}

\drawedge[ELside=r,ELdist=2.0](n31,n32){b}

\drawedge[ELdist=2.0](n31,n34){a}

\drawedge[ELdist=2.0](n32,n33){a}

\drawedge[ELdist=2.0](n34,n35){b}

\drawedge[ELdist=2.0](n33,n35){a}

\drawedge[ELdist=2.0,sxo=1.0,exo=1.0](n34,n33){ a}

\drawedge[ELdist=2.0](n33,n34){b}

\drawbpedge[ELside=r,ELdist=2.0](n32,-90,19.99,n35,-89,37.16){b}

\end{picture}
\end{center}
\end{Ex}

\normalsize

\begin{Exo}
 On donne un AFD par la table de transition des Ã©tats suivante :
$$\begin{array}{|c||c|c|}
   \hline
t &amp; a &amp; b\\
\hline
0 &amp; 1 &amp; 2 \\
1 &amp; 5 &amp; 3 \\
2 &amp; 5 &amp; 1 \\
3 &amp; 4 &amp; 5 \\
4 &amp; 5 &amp; 4 \\
5 &amp; 5 &amp; 5 \\
\hline
\end{array}$$

\'Etat initial : 0

\'Etats d'acceptation : 4


\noindent Cet automate reconnaÃ®t le langage dÃ©fini par l'expression rÃ©guliÃ¨re $(a|bb)bab^*$.

\noindent Appliquer la mÃ©thode de l'Ã©quivalence de NÃ©rode pour trouver l'automate minimal reconnaissant le langage.
\end{Exo}


\begin{Exo}
Faire de mÃªme avec l'automate de Moore dont la table de transition est :
$$\begin{array}{|c||c|c|}
   \hline
t &amp; a &amp; b\\
\hline
a &amp; a &amp; c \\
b &amp; g &amp; d \\
c &amp; f &amp; e \\
d &amp; a &amp; d \\
e &amp; a &amp; d \\
f &amp; g &amp; f \\
g &amp; g &amp; c \\
\hline
\end{array}
$$
\end{Exo}


\section{MÃ©thode du dual}

\subsection{Dual d'un automate}

Soit $M = (E,I,t,S,A)$ un automate quelconque (AFD ou AFND).

\begin{Def}
L'automate dual de $M$ est l'automate $M^{-1} = (E,I,t',A,S)$, oÃ¹ $t'$ est la relation sur $E$ obtenue en renversant toutes les flÃ¨ches sur le graphe de $M$, c'est-Ã&nbsp;-dire si $R' \subset (E \times I) \times E$ est le graphe de la relation $t'$, alors que le graphe de $t$ est $R$, on a
$$((e,i),e') \in R' \Longleftrightarrow ((e',i),e) \in R$$
\end{Def}

Il est clair que $M$ reconnaÃ®t un mot $w \in I^*$ si et seulement si $M^{-1}$ reconnaÃ®t le mot $w^{-1}$ (si $w = a_1 a_2 \hdots a_n$, alors $w^{-1} = a_n a_{n-1} \hdots a_1$).

Le dual d'un automate Ã&nbsp; comportement dÃ©terminÃ© n'est pas nÃ©cessairement Ã&nbsp; comportement dÃ©terminÃ©.


\subsection{MÃ©thode du dual}

Soit $M$ un automate de Moore :

\begin{enumerate}
 \item Construire l'automate dual $M^{-1}$ de $M$.
 \item Appliquer la construction par sous-ensembles Ã&nbsp; $M^{-1}$ pour le transformer en automate $M'$ de Moore.
 \item Construire le dual ${M'}^{-1}$ de $M'$.
 \item Appliquer la construction par sous-ensemble Ã&nbsp; ${M'}^{-1}$ pour obtenir l'automate de Moore $M''$.
\end{enumerate}

L'automate $M''$ est l'automate minimal tel que $\mathcal{L}(M'') = \mathcal{L}(M)$.



\begin{Exo}
 On donne un AFD par la table de transition des Ã©tats suivante :
$$\begin{array}{|c||c|c|}
   \hline
t &amp; a &amp; b\\
\hline
0 &amp; 1 &amp; 2 \\
1 &amp; 3 &amp; 4 \\
2 &amp; 3 &amp; 4 \\
3 &amp; 5 &amp; 6 \\
4 &amp; 5 &amp; 6 \\
5 &amp; 7 &amp; 8 \\
6 &amp; 7 &amp; 8 \\ 
7 &amp; 9 &amp; 10 \\
8 &amp; 9 &amp; 10 \\
9 &amp; 11 &amp; 12 \\
10 &amp; 11 &amp; 12 \\ 
11 &amp; 1 &amp; 2 \\
12 &amp; 1 &amp; 2 \\
\hline
  \end{array}
$$

\'Etat initial : 0

\'Etats d'acceptation : 0 3 4 5 6 7 8 11 12


\noindent Cet automate reconnaÃ®t le langage dÃ©fini par l'expression rÃ©guliÃ¨re $((a|b)^2)^* | ((a|b)^3)^*$.

\noindent  Appliquer la mÃ©thode du dual pour trouver l'automate minimal reconnaissant le langage.
\end{Exo}



\begin{Exo}
 On donne un automate non dÃ©terministe, Ã&nbsp; transitions instantannÃ©es, par la table de transition suivante :
$$\begin{array}{|c||c|c|c|}
   \hline
t &amp; \varepsilon &amp; a &amp; b\\
\hline
0 &amp; 1,11 &amp;   &amp; \\
1 &amp; 2, 7 &amp;   &amp; \\
2 &amp;      &amp;   &amp; 3 \\
3 &amp; 4, 6 &amp;   &amp; \\
4 &amp;      &amp; 5 &amp; \\
5 &amp; 4, 6 &amp;   &amp; \\
6 &amp; 10   &amp;   &amp; \\ 
7 &amp;      &amp; 8 &amp; \\
8 &amp;      &amp;   &amp; 9 \\
9 &amp; 10   &amp;   &amp; \\ 
10 &amp; 22  &amp;   &amp; \\ 
11 &amp; 12,14 &amp; &amp; \\
12 &amp;     &amp; 13 &amp; \\
13 &amp;     &amp;    &amp; \\
14 &amp; 17    &amp;    &amp; 15 \\
15 &amp;     &amp;    &amp; 16 \\
16 &amp;  17   &amp;    &amp; \\
17 &amp;     &amp; 18   &amp; \\
18 &amp; 19,21    &amp;    &amp; \\
19 &amp;     &amp;    &amp; 20 \\
20 &amp; 19,21    &amp;    &amp; \\
21 &amp;  22   &amp;    &amp; \\
22 &amp;     &amp;    &amp; \\
\hline
  \end{array}
$$

\'Etat initial : 0


\'Etat d'acceptation : 22



\noindent Cet automate reconnaÃ®t le langage dÃ©fini par l'expression rÃ©guliÃ¨re $ba^* | ab | (a | bb) ab^*$.

\noindent Le dÃ©terminiser, puis lui appliquer la mÃ©thode de votre choix pour obtenir l'automate minimal reconnaissant le langage.
\end{Exo}






\begin{Exo}
 On donne la table de transition suivante pour un automate fini :
$$\begin{array}{|c||c|c|}
\hline
   t &amp; a &amp; b \\
 \hline
0 &amp; 1 &amp; 2 \\
\hline
1 &amp; 3 &amp; 4 \\
\hline
2 &amp; 5 &amp; 6 \\
\hline
3 &amp; 1 &amp; 2 \\
\hline
4 &amp; 7 &amp; 8 \\
\hline
5 &amp; 7 &amp; 8 \\
\hline
6 &amp; 1 &amp; 2 \\
\hline
7 &amp; 9 &amp; 10 \\
\hline
8 &amp; 10 &amp; 11 \\
\hline
9 &amp; 7  &amp; 8 \\
\hline
10 &amp; 10 &amp; 10 \\
\hline
11 &amp; 7 &amp; 8 \\
\hline
  \end{array}
$$

L'Ã©tat initial est 0, et les Ã©tats d'acceptation sont 4, 5, 9 et 11.\\

\noindent Appliquer Ã&nbsp; cet automate l'algorithme de votre choix pour obtenir l'automate minimal reconnaissant le mÃªme langage (Ã©quivalence de NÃ©rode ou dual).

(L'automate minimal possÃ¨de 7 Ã©tats).
\end{Exo}

\section{SynthÃ¨se}

\subsection{Outils}

\subsubsection{Construction par sous-ensemble}


\begin{description}
\item[Domaine d'application : ] Cette mÃ©thode s'applique aux automates finis non dÃ©terministes. Il est aussi possible de l'utiliser sur un AFD, mais c'est sans intÃ©rÃªt.
\item[RÃ©sultat : ] Automate reconnaissant le mÃªme langage.
\item[But : ] Obtenir un AFD reconnaissant le mÃªme langage.
\item[Autre utilisation : ] Peut permettre d'obtenir l'automate minimal reconnaissant le mÃªme langage (mÃ©thode du dual).
\end{description}

\subsubsection{\'Equivalence de NÃ©rode}

\begin{description}
\item[Domaine d'application : ] Cette mÃ©thode ne s'applique qu'aux automates finis dÃ©\-ter\-mi\-nis\-tes (AFD).
\item[RÃ©sultat : ] Le quotient de l'automate considÃ©rÃ© par l'Ã©quivalence de NÃ©rode ; un automate ne reconnaissant gÃ©nÃ©ralement pas le mÃªme langage.
\item[But : ] Simplifier l'automate considÃ©rÃ©, si c'est possible, grÃ¢ce Ã&nbsp; la mÃ©thode des quotients.
\end{description}

\subsection{MÃ©thodes d'optimisation}

\subsubsection{MÃ©thode des quotients}

\begin{description}
\item[Domaine d'application : ] Cette mÃ©thode ne s'applique qu'aux automates finis dÃ©\-ter\-mi\-nis\-tes (AFD).
\item[Moyens : ] \'Equivalence de NÃ©rode.
\item[RÃ©sultat : ] On obtient l'automate minimal reconnaissant le mÃªme langage.
\end{description}

\subsubsection{MÃ©thode du dual}

\begin{description}
\item[Domaine d'application : ] Cette mÃ©thode ne s'applique qu'aux automates finis dÃ©\-ter\-mi\-nis\-tes (AFD).
\item[Moyens : ] Construction par sous-ensembles.
\item[RÃ©sultat : ] L'automate de Moore minimal reconnaissant le mÃªme langage.
\item[EfficacitÃ© : ] \'ElÃ©gant, mais pas efficace.
\end{description}


\gsaut
\centerline{\x{Fin du Chapitre}}

</pre></body></html>