t

[cours-maths-dis.git] / automates / AutomatesFinis.tex

\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 à 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 à 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 à 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 à 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 à 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 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 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 à comportement déterminé}


\subsection{Définition}
\begin{Def}[Automate fini à comportement déterminé]
On appelle \index{automate!fini!à comportement déterminé} \emph{automate fini à 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 à l'entrée $i \in I$ en passant à 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 & 0 & 1 \\ \hline e_0 & e_0 & e_1 \\ e_1 & e_1 & 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 & 0 & 1 & 2\\
\hline
r & s & r & u \\
s & r & r & s \\
u & u & r & 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}
  & 0 & 1\\
\hline
p & r & p \\
q & q & q \\
r & r & q \\
s & s & 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<E,I> \rightarrow V$, où $t<E,I>$ 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 & 0 & 1 \\ \hline e_0 & e_1 & e_3 \\ e_1 & e_2 & e_2 \\ e_2 & e_3 & e_2 \\ e_3 & e_3 & 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-à-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 à la paire booléenne $\{FAUX, VRAI\}$ ou $\{0,1\}$,
\begin{itemize}
 \item tout état qui donne lieu à FAUX est appelé \emph{état de rejet}\index{état!de rejet},
 \item tout état qui donne lieu à 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é à 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 à 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é à 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é à $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 & 0 & 1 \\
 \hline
e_0 & e_1 & e_2 \\
e_1 & e_1 & e_2 \\
e_2 & e_2 & 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 à comportement non déterminé}


\subsection{Définitions et exemples}

Les automates considérés jusqu'à 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} à é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 & a & b & c \\ \hline \{e_0\} & \{e_1, e_3\}  & \{e_3\} & \varnothing \\ \{e_1\} & \{e_1\} & \varnothing & \{e_2, e_3\} \\ \{e_2\} & \{e_2\} & \{e_2\} & \{e_1\} \\ \{e_3\} & \{e_3\} & \{e_3\} & \{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 à un état d'acceptation. \\
\end{Def}


\begin{Ex}
Dans l'exemple précédent,
\begin{itemize}
\item Comme $e_1$ est à 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é à un AFND. Il est constitué de l'ensemble des mots qui, depuis l'un des états initiaux, peut conduire à 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 & 0 & 1 \\
 \hline
e_0 & e_0, e_1 & e_1 \\
e_1 & - & e_2 \\
e_2 & e_2 & e_1 \\
e_3 & - & 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 à 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 à é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 à 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-à-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 à 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 à 1 modulo 4.
\end{enumerate}
\end{Exo}


\subsection{Propriétés d'un automate à $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 à $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 à 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à 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}}