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

\section{Automates finis}


\subsection{Introduction}

On va dÃ©gager dans ce paragraphe la notion de \emph{machine} comme modÃ¨le conceptuel pour la description de dispositifs informatiques aussi variÃ©s qu'un ordinateur entier, un logiciel ou un compilateur.

\begin{Def}[Machine]
Une \emph{machine}\index{machine} est un dispositif dotÃ© d'un certain nombre d'Ã©tats, susceptible d'Ã©voluer d'un Ã©tat Ã&nbsp; un autre en fonction de divers paramÃ¨tres, comme le temps (la machine est alors dotÃ©e d'une machine interne).

Elle est de plus apte Ã&nbsp; communiquer avec l'extÃ©rieur : elle peut accepter des donnÃ©es en provenance de l'extÃ©rieur (des entrÃ©es) ou communiquer des rÃ©sultats Ã&nbsp; l'extÃ©rieur (des sorties).
\end{Def}

\begin{Exo}
Donnez des exemples de machines.
\end{Exo}


\begin{Rem}
\`A chaque instant, la condition interne de la machine, y compris la mÃ©moire, constitue son Ã©tat.
\end{Rem}


\subsection{MÃ©canismes}

C'est le type le plus simple de machine :

\begin{Def}[MÃ©canisme]
Un \emph{mÃ©canisme}\index{mÃ©canisme} est totalement impermÃ©able au monde extÃ©rieur, il n'accepte aucune entrÃ©e ni aucune sortie.

C'est une machine Ã&nbsp; nombre fini d'Ã©tats, dont le comportement est gouvernÃ© uniquement par le temps, mesurÃ© par une horloge interne.
\end{Def}

\begin{Exo}
 Donner un exemple de mÃ©canisme.
\end{Exo}


Un mÃ©canisme peut Ãªtre entiÃ¨rement dÃ©crit par un couple $(E,t)$, oÃ¹ $E$ est un ensemble fini d'Ã©tats et $t : E \rightarrow E$ est une fonction de transition des Ã©tats.

\begin{Th}[Existence d'un cycle]
Un mÃ©canisme entre nÃ©cessairement dans une boucle infinie (on dit : \emph{un cycle} \index{cycle}).
\end{Th}


\noindent En effet, le nombre d'Ã©tats est fini.


\begin{Def}[\'Etat-repos]
S'il existe un Ã©tat $e \in E$ tel que $t(e)=e$, cet Ã©tat est appelÃ© \emph{Ã©tat-repos} \index{Ã©tat-repos}.
\end{Def}


\begin{Rem}
Un mÃ©canisme qui entre dans un tel Ã©tat n'en sort Ã©videmment plus.
\end{Rem}



\begin{Ex}
 Un feu de circulation routiÃ¨re peut Ãªtre dÃ©crit par un mÃ©canisme Ã&nbsp; trois Ã©tats : $V$, $O$ et $R$, donc $E=\{V,O,R\}$.

La fonction de transition des Ã©tats est telle que $t(V)=O, t(O)=R$ et $t(R)=V$.

On peut reprÃ©senter ce mÃ©canisme par le graphe de transition des Ã©tats

\begin{center}
\unitlength = 1mm 
\begin{picture}(51,39)(0,-39)
\put(0,-39){}
\node[NLangle=0.0](n0)(12.0,-12.0){R}

\node[NLangle=0.0](n1)(44.0,-12.0){V}

\node[NLangle=0.0](n2)(28.0,-32.0){O}

\drawedge(n1,n2){}

\drawedge(n2,n0){}

\drawedge(n0,n1){}



\end{picture}
\end{center}


\noindent ou par la matrice boolÃ©enne $T$ reprÃ©sentant $t$ :

$$
T = \left( \begin{array}{ccc} 0 &amp; 0 &amp; 1 \\ 1 &amp; 0 &amp; 0 \\ 0 &amp; 1 &amp; 0 \end{array} \right)
$$
\end{Ex}


\begin{Exo}
L'exemple prÃ©cÃ©dent possÃ¨de-t-il un cycle ? un Ã©tat-repos ? Sinon, le modifier pour.
\end{Exo}



\section{Automates finis Ã&nbsp; comportement dÃ©terminÃ©}


\subsection{DÃ©finition}
\begin{Def}[Automate fini Ã&nbsp; comportement dÃ©terminÃ©]
On appelle \index{automate!fini!Ã&nbsp; comportement dÃ©terminÃ©} \emph{automate fini Ã&nbsp; comportement dÃ©terminÃ©}(AFD) tout triplet $(E,I,t)$, oÃ¹
\begin{itemize}
 \item $E$ est un ensemble fini (l'ensemble des \emph{Ã©tats}),
 \item $I$ est le \emph{vocabulare} de l'automate : c'est l'ensemble fini des symboles admis en entrÃ©e,
 \item $t : E \times I \rightarrow E$ est la \emph{fonction de transition d'Ã©tats} : si l'automate se trouve dans l'Ã©tat $e \in E$, il rÃ©agit Ã&nbsp; l'entrÃ©e $i \in I$ en passant Ã&nbsp; l'Ã©tat $t(e,i)$.
\end{itemize}


Pour $i \in I$, on dÃ©finit la fonction $t_i : E \rightarrow E$ par $t_i(e) = t(i,e)$. 
\end{Def}



\begin{Ex}
 Soit $E=\{e_0,e_1\}$, $I=\{0,1\}$ et $t$ telle que
\begin{enumerate}
 \item l'entrÃ©e 0 laisse inchangÃ© chacun des Ã©tats,
 \item l'entrÃ©e 1 Ã©change les Ã©tats.
\end{enumerate}

Un tel dispositif, en Ã©lectronique, est appelÃ© un \emph{T-flip-flop} \index{T-flip-flop}, il est abondamment utilisÃ© dans les ordinateurs...

\begin{center}
 \includegraphics[scale=0.6]{automates/AutomateFiniDeterministe.eps}
\end{center}

La table qui donne les valeurs de la fonction $t$ est appelÃ©e \emph{table de transition d'Ã©tats}\index{table de transition d'Ã©tats} de l'automate considÃ©rÃ© :

$$
 \begin{array}{c|cc} t &amp; 0 &amp; 1 \\ \hline e_0 &amp; e_0 &amp; e_1 \\ e_1 &amp; e_1 &amp; e_0 \end{array} 
$$
\end{Ex}


\begin{Exo}
ReprÃ©senter le graphe de l'automate fini $M$ dont la table de transition des Ã©tats est
$$\begin{array}{c|ccc}
   t &amp; 0 &amp; 1 &amp; 2\\
\hline
r &amp; s &amp; r &amp; u \\
s &amp; r &amp; r &amp; s \\
u &amp; u &amp; r &amp; u
  \end{array}
$$
\end{Exo}

\noindent RÃ©ponse :


\begin{center}
\unitlength = 1 mm
\begin{picture}(99,36)(0,-36)
\put(0,-36){}
\node[NLangle=0.0](n0)(12.0,-20.0){u}

\node[NLangle=0.0](n1)(48.0,-20.0){r}

\node[NLangle=0.0](n2)(84.0,-20.0){s}

\drawedge[curvedepth=8.0](n0,n1){1}

\drawedge[curvedepth=8.0](n1,n2){0}

\drawedge[curvedepth=8.0](n2,n1){0,1}

\drawedge[curvedepth=8.0](n1,n0){2}

\drawloop(n0){0,2}

\drawloop(n1){1}

\drawloop(n2){2}
\end{picture} 
\end{center}


\begin{Exo}

\'Ecrire la table de transition d'Ã©tats de l'automate dont le graphe est reprÃ©sentÃ© dans la figure suivante :\\

\unitlength = 1mm 
\begin{center}

\begin{picture}(70,66)(0,-66)
\put(0,-66){}
\node[NLangle=0.0](n0)(12.02,-12.0){s}

\node[NLangle=0.0](n1)(40.02,-12.0){p}

\node[NLangle=0.0](n2)(40.02,-36.0){r}

\node[NLangle=0.0](n3)(12.02,-36.0){q}

\drawloop[ELdist=2.1,loopangle=135.0](n0){0}

\drawloop[ELdist=2.1,loopangle=40.03](n1){1}

\drawloop[ELdist=2.1,loopangle=-49.25](n2){0}

\drawloop[ELpos=40,ELdist=2.1,loopangle=220.49](n3){0,1}

\drawedge[ELdist=1.9](n0,n1){1}

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

\drawedge[ELdist=2.5](n2,n3){1}
\end{picture}
\end{center}
\end{Exo}

\noindent RÃ©ponse : 
$$
\begin{array}{c|cc}
  &amp; 0 &amp; 1\\
\hline
p &amp; r &amp; p \\
q &amp; q &amp; q \\
r &amp; r &amp; q \\
s &amp; s &amp; p 
\end{array}
$$

\subsection{Automates finis avec sorties (machines de Moore et de Mealy)}

\begin{Def}[Machine de Moore]
Une \emph{machine de Moore} est un sextuplet $M=(E,I,t,e_0,V,g)$ tel que $(E,I,t)$ est un AFD, et

\begin{itemize}
 \item $e_0 \in E$ est un Ã©tat appelÃ© \emph{Ã©tat initial}, dans lequel se trouve la machine au dÃ©part de chaque exÃ©cution.
 \item $V$ est un ensemble fini, dit \emph{ensemble des sorties},
\item $g:t&lt;E,I&gt; \rightarrow V$, oÃ¹ $t&lt;E,I&gt;$ est l'image de $t$, est la \emph{fonction de sortie} telle que, chaque fois que la machine entre dans l'Ã©tat $e$, elle produise la sortie $g(e) \in V$. 
\end{itemize}
\end{Def}




\begin{Ex}
Ici, $E=\{e_0, e_1, e_2, e_3\}$, $I=\{0,1\}$, $V=\{a,b,c\}$, $t$ est donnÃ©e, soit par le graphe de l'automate :

\unitlength = 1mm 
\scriptsize
\begin{center}
\begin{picture}(72,60)(0,-60)
\put(0,-60){}
\node[NLangle=0.0,Nmarks=i](n1)(20.01,-12.0){$e_0$}

\node[NLangle=0.0](n2)(48.01,-12.0){$e_1$:a}

\node[NLangle=0.0](n3)(48.01,-36.0){$e_2$:c}

\node[NLangle=0.0](n4)(20.01,-36.0){$e_3$:b}

\drawedge[ELdist=2.8](n2,n3){0,1}

\drawedge[ELside=r,ELdist=2.0](n1,n4){1}

\drawedge[ELdist=2.0](n1,n2){0}

\drawedge[ELside=r,ELdist=2.8,syo=0.8,eyo=0.8](n3,n4){0}

\drawedge[ELside=r,ELdist=2.5](n4,n3){1}

\drawloop[ELdist=1.9,loopangle=-51.71](n3){1}

\drawloop[ELdist=2.1,loopangle=227.17](n4){0}
\end{picture}
\end{center}

\normalsize
\noindent soit par la table de transition d'Ã©tats

$$
 \begin{array}{c|cc} t &amp; 0 &amp; 1 \\ \hline e_0 &amp; e_1 &amp; e_3 \\ e_1 &amp; e_2 &amp; e_2 \\ e_2 &amp; e_3 &amp; e_2 \\ e_3 &amp; e_3 &amp; e_2 \end{array}
$$ 

$g$ se lit dans le graphe : $g(e_1) = a, g(e_2) = c, g(e_3) = b$.
\end{Ex}

\begin{Rem}
Une telle machine est aussi appelÃ©e \emph{traducteur} \index{traducteur} (elle \og  traduit \fg{} l'entrÃ©e 0001001 en une sortie $acbcbbc$). 
\end{Rem}


\begin{Def}[Machine de Mealy]
On obtient une \emph{machine de Mealy} \index{machine!de Mealy} lorsque la sortie est dÃ©terminÃ©e, non pas par l'Ã©tat atteint, mais par la transition d'Ã©tats.

C'est donc un sextuplet $(E,I,t,e_0,V,h)$ oÃ¹ la fonction de sortie $h$ est une application de $E \times I$ vers $V$. 
\end{Def}


\begin{Rem}
Il est clair que, pour une machine de Moore $(E,I,t,e_0,V,g)$, on peut dÃ©finir une machine de Mealy Ã©quivalente (c'est-Ã&nbsp;-dire qui produit la mÃªme sortie sur toute sÃ©quence d'entrÃ©e), en posant $h(e,i) = g(t(e,i))$, soit $h = g o t$.

RÃ©ciproquement, en introduisant au besoin des Ã©tats supplÃ©mentaires, on montre qu'on peut remplacer toute machine de Mealy par une machine de Moore Ã©quivalente. 
\end{Rem}



Nous ne nous occuperons donc dans la suite que de machines de Moore.


\subsection{Automates de Moore}


\begin{Def}[Automate de Moore]
 Une machine de Moore telle que l'ensemble $V$ des sorties est rÃ©duit Ã&nbsp; la paire boolÃ©enne $\{FAUX, VRAI\}$ ou $\{0,1\}$,
\begin{itemize}
 \item tout Ã©tat qui donne lieu Ã&nbsp; FAUX est appelÃ© \emph{Ã©tat de rejet}\index{Ã©tat!de rejet},
 \item tout Ã©tat qui donne lieu Ã&nbsp; la sortie VRAI est appelÃ© \emph{Ã©tat d'acceptation} \index{Ã©tat!d'acceptation}.
\end{itemize}

\noindent est appelÃ©e \emph{automate de Moore}\index{automate!de Moore} ou \emph{machine d'acceptation}\index{machine!d'acceptation}.
\end{Def}


\begin{Rem}
Inutile d'exhiber ici la fonction de sortie, il suffit de se donner l'ensemble $A$ des Ã©tats d'acceptation, sous-ensemble de $E$.

Un automate de Moore est donc dÃ©fini par le quintuplet $(E,I,t,e_0,A)$. 
\end{Rem}



Sur le graphe reprÃ©sentant un automate de Moore, on reprÃ©sentera un Ã©tat d'acceptation en l'entourant d'un double cercle.

Les autres Ã©tats (simplement cerclÃ©s) sont les Ã©tats de rejet.


\section{Langage associÃ© Ã&nbsp; un automates de Moore}

\subsection{DÃ©finition du langage}

Soit $M$ un automate de Moore.\\

L'ensemble des entrÃ©es $I$ peut Ãªtre considÃ©rÃ© comme l'alphabet d'un systÃ¨me formel.

L'ensemble des \og  mots \fg{}  construits avec cet alphabet (suite d'Ã©lÃ©ments de l'alphabet) qui conduisent la machine Ã&nbsp; un Ã©tat d'acceptation peut Ãªtre considÃ©rÃ© comme l'ensemble des formules bien formÃ©es de ce systÃ¨me formel.

\begin{Def}[Langage]
Ce systÃ¨me formel constitue le \emph{langage  associÃ© Ã&nbsp; l'automate} $M$. 
\end{Def}

\begin{Notation}
 $\mathcal{L}(M)$
\end{Notation}

RÃ©ciproquement, Ã©tant donnÃ© un langage $\cal L$, on peut Ã©ventuellement construire un automate de Moore $M$ tel que le langage associÃ© Ã&nbsp; $M$ soit $\cal L $ : $\mathcal{L} = \mathcal{L} (M)$.

\begin{Rem}
Cela n'est pas possible pour tous les langages. Quand c'est possible, cet automate analyse les mots du langage.
\end{Rem}


\subsection{Exemple et exercices}


\begin{Ex}
Construction de l'automate qui reconnaÃ®t le langage dÃ©fini par l'expression suivante...

Un mot du langage est constituÃ© d'un nombre quelconque, mais non nul, de 0, suivi d'un nombre quelconque, mais non nul, de 1.

\begin{center}
\unitlength = 1mm 
\begin{picture}(70,67)(0,-67)
\put(0,-67){}
\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=2.0,loopangle=37.45](n1){0,1}

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

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

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

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

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

\drawloop[ELdist=2.0,loopangle=-38.44](n3){1}



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



\begin{Exo}
 DÃ©crire le langage $\mathcal{L}(M)$ de l'automate de Moore $M$ dont la table de transition des Ã©tats est :

$$\begin{array}{c|cc}
   t &amp; 0 &amp; 1 \\
 \hline
e_0 &amp; e_1 &amp; e_2 \\
e_1 &amp; e_1 &amp; e_2 \\
e_2 &amp; e_2 &amp; e_1 \\
  \end{array}
$$

L'Ã©tat initial est $e_0$ et le seul Ã©tat d'acceptation est $e_2$.
\end{Exo}

\noindent RÃ©ponse : Les mots corrects contiennent un nombre impair de 1.

\begin{Exo}
 Sur l'alphabet $I = \{0,1\}$, construire l'automate de Moore dont le langage est l'ensemble de tous les mots sur $I$ se terminant par 10.
\end{Exo}


\noindent RÃ©ponse :

\begin{center}
 \unitlength = 1mm
\begin{picture}(85,33)(0,-33)
\put(0,-33){}
\node[NLangle=0.0,Nmarks=i](n3)(20.0,-16.0){$e_0$}

\node[NLangle=0.0](n4)(48.0,-16.0){$e_1$}

\node[NLangle=0.0,Nmarks=r](n5)(76.0,-16.0){$e_2$}

\drawedge[curvedepth=8.0](n3,n4){1}

\drawedge[curvedepth=8.0](n4,n5){0}

\drawedge[curvedepth=5.0](n5,n4){1}

\drawedge[curvedepth=15.0](n5,n3){0}

\drawloop(n3){0}

\drawloop(n4){1}
\end{picture}
\end{center}


\begin{Exo}
 Construire un automate de Moore dont l'alphabet est constituÃ© des lettres du mot \og ALGUE\fg{}  qui reconnaÃ®t les mots contenant la sous-chaÃ®ne \og GEL\fg{}  (et seulement celle-ci).
\end{Exo}

\noindent RÃ©ponse :

\begin{center}
 \unitlength = 1mm
\begin{picture}(117,46)(0,-46)
\put(0,-46){}
\node[NLangle=0.0,Nmarks=i](n3)(20.0,-16.0){$e_0$}

\node[NLangle=0.0](n4)(48.0,-16.0){$e_1$}

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

\drawedge[curvedepth=8.0](n3,n4){G}

\drawedge[curvedepth=8.0](n4,n5){E}

\drawedge[curvedepth=18.46](n5,n3){A,G,U,E}

\drawloop(n3){A,L,U,E}

\drawloop(n4){G}

\node[NLangle=0.0,Nmarks=r](n6)(104.0,-16.0){$e_3$}

\drawedge[ELside=r,ELdist=2.2,curvedepth=8.0](n4,n3){A,L,U}

\drawedge[curvedepth=8.0](n5,n6){L}

\drawloop(n6){A,L,G,U,E}



\end{picture}
\end{center}


\section{Automates finis Ã&nbsp; comportement non dÃ©terminÃ©}


\subsection{DÃ©finitions et exemples}

Les automates considÃ©rÃ©s jusqu'Ã&nbsp; prÃ©sent ont un comportement complÃ¨tement \og dÃ©\-ter\-mi\-nÃ© \fg{} : pour chaque configuration Ã©tat-entrÃ©e $(e,i) \in E \times I$, une et une seule transition d'Ã©tat est fixÃ©e.

Cela rÃ©sulte du fait qu'ils sont rÃ©gis par une \emph{fonction} de transition d'Ã©tats $t$ (de $E \times I$ dans $E$).\\

On peut imaginer des automates moins \og rigides \fg{}, pour lesquels, dans certaines configurations, plusieurs transitions d'Ã©tats sont possibles ou, au contraire, aucune n'est prÃ©vue.

Pour un tel automate, qualifiÃ© de non-dÃ©terministe, $t$ n'est plus une fonction, mais une relation binaire quelconque. Ainsi...

\begin{Def}[Automate fini non dÃ©terministe]
Un \emph{automate fini non dÃ©terministe}\index{automate!fini!non dÃ©terministe} Ã&nbsp; Ã©tats d'acceptation est dÃ©fini par $(E,I,t,S,A)$ oÃ¹ :
\begin{itemize}
\item $E$ est un ensemble (fini) d'Ã©tats,
\item $I$ est l'ensemble des entrÃ©es,
\item $t$ est la relation de transition des Ã©tats,
\item $S$, partie de $E$, est l'ensemble des Ã©tats initiaux,
\item $A$, partie de $E$, est l'ensemble des Ã©tats d'acceptation.
\end{itemize}
\end{Def}

\begin{Rem}
Il se peut donc qu'une entrÃ©e puisse conduire un automate vers plusieurs Ã©tats possibles ou qu'elle laisse l'automate indiffÃ©rent.
\end{Rem}

\begin{Ex}

Dans cet exemple, lorsque l'automate se trouve dans l'Ã©tat $e_0$, l'entrÃ©e $a$ peut le faire passer dans l'Ã©tat $e_1$ ou dans l'Ã©tat $e_3$ et, lorsqu'il se trouve dans l'Ã©tat $e_1$, rien n'est prÃ©vu pour l'entrÃ©e $b$.


\begin{center}
\unitlength = 1mm 
\begin{picture}(51,53)(0,-53)
\put(0,-53){}
\node[NLangle=0.0,Nmarks=i](n8)(12.01,-20.0){$e_0$}

\node[NLangle=0.0](n9)(36.01,-20.0){$e_3$}

\node[NLangle=0.0,Nmarks=r](n10)(36.01,-44.0){$e_2$}

\node[NLangle=0.0,Nmarks=ir](n11)(12.01,-44.0){$e_1$}

\drawedge[ELdist=2.2](n8,n9){a,b}

\drawedge[ELside=r,ELdist=2.1](n8,n11){a}

\drawedge[ELdist=2.0,sxo=0.9,exo=0.9](n11,n9){c}

\drawedge[ELdist=2.7,syo=0.9,eyo=0.9](n11,n10){c}

\drawedge[ELdist=2.4](n10,n11){c}

\drawloop[ELdist=2.2](n9){a,b,c}

\drawloop[ELdist=2.2,loopangle=270](n11){a}

\drawloop[ELdist=2.2](n10){a,b}



\end{picture}

\end{center}

Table de transitions

$$
 \begin{array}{c|ccc} t &amp; a &amp; b &amp; c \\ \hline \{e_0\} &amp; \{e_1, e_3\}  &amp; \{e_3\} &amp; \varnothing \\ \{e_1\} &amp; \{e_1\} &amp; \varnothing &amp; \{e_2, e_3\} \\ \{e_2\} &amp; \{e_2\} &amp; \{e_2\} &amp; \{e_1\} \\ \{e_3\} &amp; \{e_3\} &amp; \{e_3\} &amp; \{e_3\} \end{array}
$$
\end{Ex}

Il est Ã©videmment possible de concevoir des AFND produisant des sorties, et, en particulier, des Ã©tats d'acceptation et de rejet. On admettra par ailleurs qu'il puisse y avoir, dans ces cas, plusieurs Ã©tats initiaux possibles.\\

Soit alors $M=(E,I,t,S,A)$ un AFND.

\begin{Def}[entrÃ©e reconnue]
On dit qu'une suite $w$ d'entrÃ©es est \emph{reconnue} \index{reconnue} par l'automate si cette suite \emph{peut} conduire l'automate Ã&nbsp; un Ã©tat d'acceptation. \\
\end{Def}


\begin{Ex}
Dans l'exemple prÃ©cÃ©dent,
\begin{itemize}
\item Comme $e_1$ est Ã&nbsp; la fois un Ã©tat initial et d'acceptation, le mot vide fait partie du langage reconnu par l'automate.
\item Le mot $aaacc$ est reconnu par l'automate.
\item Les mots refusÃ©s sont ceux qui n'ont aucun chemin vers un Ã©tat d'acceptation, comme $bbb$.
\end{itemize}
\end{Ex}


On dÃ©finit aussi de cette maniÃ¨re le langage $\mathcal{L}(M)$ associÃ© Ã&nbsp; un AFND. Il est constituÃ© de l'ensemble des mots qui, depuis l'un des Ã©tats initiaux, peut conduire Ã&nbsp; l'un des Ã©tats d'acceptation.

\begin{Exo}
 On considÃ¨re l'automate fini $M$ non dÃ©terministe dont la relation de transition des Ã©tats est donnÃ©e par la table
$$\begin{array}{|c||c|c|}
   \hline
  t &amp; 0 &amp; 1 \\
 \hline
e_0 &amp; e_0, e_1 &amp; e_1 \\
e_1 &amp; - &amp; e_2 \\
e_2 &amp; e_2 &amp; e_1 \\
e_3 &amp; - &amp; e_0, e_1, e_2 \\
 \hline
  \end{array}
$$

Si $e_0$ et $e_1$ sont les Ã©tats initiaux et si $e_2$ est le seul Ã©tat d'acceptation, les mots 001111 et 01001 sont-ils reconnus par $M$ ?
\end{Exo}


\noindent RÃ©ponse : 001111 est reconnu, mais pas 01001.


\subsection{UtilitÃ©}

Les AFND sont beaucoup plus simple Ã&nbsp; construire que les AFD.

Ainsi, les algorithmes de construction automatique d'automates produisent des AFND, et les algorithmes de simplification d'automate utilisent des AFND.

Mais, Ã©tant non dÃ©terministes, ils ne sont pas programmables. Heureusement, on sait les dÃ©terminiser (\emph{i.e.} construire un automate de Moore qui reconnaÃ®t le mÃªme langage)...

\section{DÃ©termination d'un AFND}

L'algorithme exposÃ© dans ce paragraphe est appelÃ© \emph{mÃ©thode de construction par sous-ensemble}\index{mÃ©thode de construction par sous-ensemble}. Il s'agit d'une mÃ©thode qui permet d'obtenir un automate de Moore qui reconnaÃ®t le mÃªme langage qu'un AFND.\\

\subsection{MÃ©thode de construction par sous-ensemble}

Soit donc $M=(E,I,t,S,A)$ un AFND Ã&nbsp; Ã©tats d'acceptation. Soit $Y$ une partie quelconque de $E$ et $x \in I$ une entrÃ©e quelconque.

\begin{Notation}
On note $Y_x$ l'ensemble des Ã©tats de $M$ accessibles Ã&nbsp; partir de l'un quelconque des Ã©tats de $Y$ sur l'entrÃ©e $x$. 
\end{Notation}

\begin{Ex}
Dans l'exemple prÃ©cÃ©dent, et pour $Y = \{ e_1, e_3\}$ :
\begin{itemize}
\item $Y_a = \{e_1\} \cup \{ e_3 \} =  \{e_1, e_3 \}$,
\item $Y_b = \{e_3\} \cup \varnothing = \{ e_3 \}$,
\item $Y_c = \{e_2, e_3\} \cup \{ e_3 \} = \{e_2, e_3 \}$,
\end{itemize}
\end{Ex}


On obtient un automate de Moore $\mathcal{M} = ( \mathcal{E}, \mathcal{I}, \mathcal{T}, E_0, \mathcal{A})$ de la maniÃ¨re suivante :

\begin{enumerate}
 \item L'ensemble $\mathcal{E}$ des Ã©tats de $\mathcal{M}$ est le sous-ensemble de $\mathcal{P}(E)$ dÃ©fini par :
\begin{itemize}
\item $S \in \mathcal{E}$,
\item $\forall x \in \mathcal{I}, \forall Y \in \mathcal{E}, Y_x \in \mathcal{E}$.
\end{itemize}
\item L'Ã©tat initial de $\mathcal{M}$ est $E_0=S$.
\item L'ensemble $\mathcal{A}$ des Ã©tats d'acceptation de $\mathcal{M}$ est dÃ©fini par $\mathcal{A}=\{Y \in \mathcal{E} \| Y \cap A \neq \emptyset \}$.
\item La fonction de transition d'Ã©tats est dÃ©finie par $\mathcal{T} : \mathcal{E} \times \mathcal{I} \rightarrow \mathcal{E}, (Y,x) \longmapsto \mathcal{T} (Y,x) = Y_x$.
\end{enumerate}

\subsection{En pratique}

En pratique, on part de l'Ã©tat initial de $\mathcal{M}$, c'est-Ã&nbsp;-dire de $S$.

Pour chacune des entrÃ©es, on forme l'ensemble $S_x$ des Ã©tats de $M$ que la relation de transition $t$ permet d'atteindre Ã&nbsp; partir de tous les Ã©tats de $S$, et on pose $\mathcal{T} (S,x) = S_x$.

On recommence l'opÃ©ration pour chacun des Ã©tats $S_x$ ainsi obtenus (pour les diverses entrÃ©es $x$), etc.



\begin{Rem}
Le processus a une fin, parce que $E$ est fini, donc aussi $\mathcal{P}(E)$ : si l'automate de dÃ©part a $n$ Ã©tats, l'automate dÃ©terminisÃ© en aura au plus $2^n$.. 
\end{Rem}

\begin{Rem}
Il se peut qu'aucun Ã©tat ne soit accessible depuis l'un quelconque des Ã©tats d'un Ã©tat $Y_x$ de $\mathcal{M}$, sur une entrÃ©e $y$.

On prend alors pour Ã©tat d'arrivÃ©e de $\mathcal{M}$ l'ensemble vide ; celui-ci constitue un Ã©tat particulier de $\mathcal{M}$, dont on ne peut sortir sur aucune entrÃ©e (\emph{c.f.} exemple ci-dessous).
\end{Rem}


\begin{Ex}
Un exemple...\\

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

\node[NLangle=0.0,iangle=128.23,Nmarks=i](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}



\node[NLangle=0.0,Nw=16.0,Nmr=2.0](n40)(68.0,-32.0){$e_0$,$e_1$}

\node[NLangle=0.0,Nmarks=r,Nw=16.0,Nmr=2.0](n41)(124.0,-44.0){$e_2$,$e_3$}

\node[NLangle=0.0,Nmarks=r,Nw=16.0,Nmr=2.0](n42)(124.0,-20.0){$e_1$,$e_3$}

\node[NLangle=0.0,Nmarks=r,Nw=16.0,Nmr=2.0](n43)(96.0,-32.0){$e_1$,$e_2$,$e_3$}

\drawedge[ELside=r,ELdist=2.0](n40,n43){0,1}

\drawedge[ELdist=2.0](n43,n42){1}

\drawedge[ELside=r,ELdist=2.0](n43,n41){0}

\node[NLangle=0.0](n45)(148.0,-8.0){$e_1$}

\node[NLangle=0.0,Nmarks=r](n46)(148.0,-32.0){$e_3$}

\node[NLangle=0.0](n47)(148.0,-56.0){$e_2$}

\node[NLangle=0.0](n48)(168.0,-32.0){$\varnothing$}

\drawedge[ELdist=2.0](n42,n45){1}

\drawedge[ELdist=2.0](n42,n46){0}

\drawedge[ELside=r,ELdist=2.0](n41,n46){1}

\drawedge[ELside=r,ELdist=2.0](n41,n47){0}

\drawedge[ELdist=2.0](n47,n46){1}

\drawedge[ELdist=2.0](n45,n46){0}

\drawedge[ELdist=2.0](n46,n48){0,1}

\drawloop[ELdist=2.0,loopangle=0.0](n45){1}

\drawloop[ELdist=2.0,loopangle=0.0](n47){0}

\drawloop[ELdist=2.0,loopangle=0.0](n48){0,1}



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



\begin{Exo}
 Construire des automates de Moore Ã©quivalents aux AFND ci-dessous :
\begin{center}

 \begin{picture}(148,67)(0,-67)
\unitlength = 1mm 
\put(0,-67){}
\node[NLangle=0.0,Nmarks=i](n4)(12.0,-19.99){3}

\node[NLangle=0.0,Nmarks=r](n5)(40.0,-19.99){4}

\node[NLangle=0.0,Nmarks=i](n6)(12.0,-44.0){0}

\node[NLangle=0.0](n7)(40.0,-44.0){1}

\node[NLangle=0.0](n8)(68.0,-44.0){2}

\node[NLangle=0.0,Nmarks=i](n9)(80.0,-28.0){0}

\node[NLangle=0.0](n10)(96.0,-12.0){1}

\node[NLangle=0.0](n11)(96.0,-44.0){2}

\node[NLangle=0.0](n12)(104.0,-28.0){3}

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

\node[NLangle=0.0,iangle=0.0,Nmarks=i](n14)(136.0,-28.0){6}

\node[NLangle=0.0,Nmarks=r](n15)(120.0,-44.0){5}

\drawedge[ELdist=2.0](n4,n5){0}

\drawedge[ELdist=2.1](n6,n4){1}

\drawedge[ELside=r,ELdist=2.1](n5,n6){1}

\drawedge(n5,n7){1}

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

\drawedge[ELside=r,ELdist=2.1](n8,n5){1}

\drawloop[ELdist=2.1](n5){0}

\drawloop[ELdist=2.1,loopangle=-59.26](n8){0}

\drawloop[ELdist=2.1,loopangle=260.34](n7){0}

\drawloop[ELdist=1.5,loopangle=-74.22](n6){0,1}

\drawedge[ELdist=2.0](n9,n10){a}

\drawedge[ELside=r,ELdist=2.1](n9,n11){a}

\drawedge[ELdist=2.1](n9,n12){a}

\drawedge[ELdist=2.1](n11,n15){b}

\drawedge[ELdist=2.0](n10,n13){b}

\drawedge[ELside=r,ELdist=2.1](n12,n13){c}

\drawedge[ELdist=2.1](n12,n15){a}

\drawedge[ELdist=2.0](n14,n13){c}

\drawedge[ELside=r,ELdist=2.1](n14,n15){a}



\end{picture}
\end{center}
\end{Exo}


\begin{Exo}
 Construire des automates de Moore reconnaissant les langages dÃ©finis par les expressions rÃ©guliÃ¨res :
\begin{enumerate}
 \item $(a|b)^* b (a|b)^*$
 \item $((a|b)^2)^* | ((a | b)^3)^*$
 \item $(a^2 | b^2)^*|(a^3|b^3)^*$
 \item $ba^*|ab|(a|bb)ab^*$.
\end{enumerate}
\end{Exo}

\noindent RÃ©ponses : Pour $(a|b)^* b (a|b)^*$

\begin{center}
 \unitlength = 1mm


\begin{picture}(63,26)(0,-26)
\put(0,-26){}
\node[NLangle=0.0,Nmarks=i](n3)(20.0,-16.0){$e_0$}

\node[NLangle=0.0,Nmarks=r](n4)(48.0,-16.0){$e_1$}

\drawloop(n3){a}

\drawloop(n4){a,b}

\drawedge(n3,n4){b}

%\drawedge(n4,n4){}

%\drawedge(n4,n4){}
\end{picture}
\end{center}


\section{Exercices}

\begin{Exo}
Soit $\Sigma = \{a, b\}$.
\begin{enumerate}
\item Fabriquer un automate qui accepte les mots de longueur pair.

\item Fabriquer un automate qui accepte les mots de longueur impair.

\item Fabriquer un automate qui accepte les mots dont la longueur est congrue Ã&nbsp; 1 modulo 4.
\end{enumerate}
\end{Exo}


\subsection{PropriÃ©tÃ©s d'un automate Ã&nbsp; $n$ Ã©tats}
\begin{Exo}
Soit un automate fini dÃ©terministe $A$ qui a $n$ Ã©tats et qui n'a pas d'Ã©tat inaccessible.

Montrer qu'il existe nÃ©cessairement un mot de longueur infÃ©rieure oÃ¹ Ã©gale Ã&nbsp; $n-1$ qui est acceptÃ© par $A$.
\end{Exo}


\subsection{Les palindromes}

\begin{Exo}[Palindrome]
Soit $\Sigma$ un alphabet dont le nombre de caractÃ¨res est su\-pÃ©\-rieur ou Ã©gal Ã&nbsp; deux.

On appelle {\em retournement} l'application 
$\rho: \Sigma^* \rightarrow \Sigma^*$ telle que 
$\rho(\epsilon) = \epsilon$ et qui associe au mot $\sigma$ de longueur non nulle le mot $\tau$, nommÃ© {\em retournÃ©} de $\sigma$ dÃ©fini par
$\tau(k) = \sigma(n-k+1)$

\begin{enumerate}

\item DÃ©terminer $\rho(\sigma)$ quand $\sigma = aabcdea$. 
D'une faÃ§on gÃ©nÃ©rale, comment le retournement opÃ¨re-t-il sur la chaÃ®ne de caractÃ¨res qui reprÃ©sente un mot?

\item Exprimer $\rho(\sigma\tau)$ en fonction de  $\rho(\sigma)$ et   $\rho(\tau)$. Que vaut $\rho(\rho(\sigma))$?

\item  On dit qu'un mot $\sigma$ est un {\em palindrome} si $\rho(\sigma) = \sigma$. 
Montrer que tout mot de la forme 
$\rho(\sigma)\sigma$ est un palindrome. 
Est-ce lÃ&nbsp; tous les palindromes?

\item  Si le nombre d'Ã©lÃ©ments de $\Sigma$ est $n$, combien y a-t-il de palindromes de longueur $p$ dans $\Sigma^*$?
\end{enumerate}
\end{Exo}




\begin{Exo}[Suite palindrome]
Soit $\Sigma=\{a,b\}$.
Construire un AFD qui accepte les palindromes de longueur 3.
\end{Exo}




\begin{Exo}
Soit $\Sigma=\{a,b\}$.
On note $L$ le langage constituÃ© des mots dans lesquels la lettre $a$, quand elle apparaÃ®t, est toujours suivie d'au moins deux lettres $b$.
\begin{enumerate}
\item Quels sont les mots de $L$ de longueur infÃ©rieure ou Ã©gale  6?

\item Construire un AFD qui accepte $L$.

\item Donner une expression rÃ©guliÃ¨re qui dÃ©crit $L$.
\end{enumerate}
\end{Exo}

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

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