Définition
Un
automate d'état finis déterministe \( \A\) , plus simplement appelé ADEF, est la donnée de
- \( \bullet\)
- un alphabet \( \Sigma_\A\) , appelé l'alphabet de l'automate,
- \( \bullet\)
- un ensemble fini \( E_\A\) d'état,
- \( \bullet\)
- un singleton \( I_\A\subset E_\A\) d'état initiale,
- \( \bullet\)
- un ensemble \( F_\A\subset E_\A\) d'états finaux,
- \( \bullet\)
- une fonction de transition \( \tau_\A : E_\A\times \Sigma_\A \longrightarrow E_\A\) .
Exemple
Considérons l'ADEF ayant \( \{0,1\}\) comme alphabet, \( \{A,B,C\}\) comme état, \( \{A\}\) comme état initial, \( \{A,C\}\) comme états finaux et ayant pour fonction de transition la fonction
\begin{eqnarray*}
\tau : E_\A\times\Sigma_\A &\longrightarrow& E_\A\\
(A,0)&\longmapsto& B\\
(B,1)&\longmapsto& C\\
(B,0)&\longmapsto& B\\
(C,1)&\longmapsto& A
\end{eqnarray*}
Représentation d'un automate
On dispose de deux moyens pour représenter un automate. Le premier, la représentation matricielle, est plus satisfaisante pour l'informaticien qui pourra programmer un automate par l'intermédiaire de cette matrice. Le second moyen, la représentation sagittale, va permettre une visualisation simple.
Définition
Soit \( \A\) un ADEF. On définit la matrice de l'automate \( M_\A\) indexée par les états en ligne et l'alphabet en colonne par :
\[(M_\A)_{e,x}=e'\qquad\text{ si }\tau_\A(e,x)=e'\]
Exemple
La matrice suivante est celle de l'automate de l'exemple précédent en précédant (resp. succédant) les états initiaux (resp. finaux) d'une petite flèche.
\[
M_\A=\begin{array}{c|cc}
&0&1\\\hline
\rightarrow A\rightarrow&B& \\
B \qquad &B&C\\
\qquad C\rightarrow &&A
\end{array}
\]
Définition
Soit \( \A\) un ADEF. On définit le graphe valué de l'automate \( \G_\A\) par :
\[\Som(\G_\A)=E_\A, \qquad \Arc(\G_\A)=\left\{(e,e')\in E_\A^2\Big| \exists x\in \Sigma,\ \tau_\A(e,x)=e'\right\}\]
où la valuation est donné par la la fonction de transition.
Exemple
Le graphe de l'automate de notre exemple est :
\[\xymatrix{
A\ar[rr]^0&&B\ar@(rd,ru)[]_0\ar[dl]^1\\
&C\ar[lu]^1&
}\]
On spécifie les états initiaux par des flèches entrantes dans les états concernés et les états finaux par des flèches sortantes
\[\xymatrix{
\ar[d]&&\\
A\ar[d]\ar[rr]^0&&B\ar@(rd,ru)[]_0\ar[dl]^1\\
&C\ar[d]\ar[lu]^1&\\
&&
}\]
Complétion
Définition
Un ADEF des appelé complet si sa fonction de transition est une application.
Exemple
Considérons \( \Sigma_\A=\{0,1\}\) , \( E_\A=\{p, i\}\) , \( I_\A=\{p\}\) , \( F_\A=\{p\}\) (\( p\) pour paire et \( i\) pour impaire) et la fonction de transition
\begin{eqnarray*}
\tau : E_\A\times\Sigma_\A &\longrightarrow& E_\A\\
(p,0)&\longmapsto& i\\
(p,1)&\longmapsto& p\\
(i,0)&\longmapsto& p\\
(i,1)&\longmapsto& i
\end{eqnarray*}
Dans un ADEF complet, tous les coefficients de la matrice sont remplis (la matrice est complète). Le graphe de cet automate est :
\[\xymatrix@C=2cm{
\ar[d]&\\
p\ar@/^2pc/[r]^0\ar@(ld,lu)[]^1\ar[d]
&i\ar@/^2pc/[l]^0\ar@(rd,ru)[]_1\\
&
}
\]
Théorème [Complétion d'un automate]
Soit \( \A\) un automate d'état finis déterministe. Considérons l'automate \( \overline{\A}\) défini en rajoutant un nouvel état \( e\) tel que :
- \( \bullet\)
- Alphabet : \( \Sigma_{\overline{\A}}=\Sigma_{{\A}}\)
- \( \bullet\)
- États : \( E_{\overline{\A}}=E_{\A}\cup\{e\}\)
- \( \bullet\)
- États initiaux :\( I_{\overline{\A}}=I_\A\)
- \( \bullet\)
- États finaux :\( F_{\overline{\A}}=F_\A\)
- \( \bullet\)
- Fonction de transition :
\begin{eqnarray*}
\tau_{\overline{\A}} : E_{\overline{\A}}\times\Sigma_{\overline{\A}}&\longrightarrow&E_{\overline{A}}\\
(x,\sigma)&\longmapsto&\left\{
\begin{array}{cr}
\tau_\A(x,\sigma)&\text{si c'est défini}\\
e&\text{sinon}
\end{array}
\right.
\end{eqnarray*}
Alors \( \overline{\A}\) , appelé le
complété de \( \A\) , est un automate d'état finis déterministe complet.
Démonstration
C'est une conséquence triviale de la construction de \( \overline{\A}\) .
Exemple
Considérons l'ADEF (non complet) \( \A\) suivant :
- \( \bullet\)
- \( \Sigma_{\A}=\{0,1\}\)
- \( \bullet\)
- \( E_\A=\{A,B,C\}\)
- \( \bullet\)
- \( I_\A=\{A,B\}\)
- \( \bullet\)
- \( F_\A=\{A,C\}\)
- \( \bullet\)
- Fonction de transition :
\begin{eqnarray*}
\tau : E_\A\times\Sigma_\A &\longrightarrow& E_\A\\
(A,0)&\longmapsto& B\\
(B,1)&\longmapsto& C\\
(B,0)&\longmapsto& B\\
(C,1)&\longmapsto& A
\end{eqnarray*}
Le complété de cette automate est :
- \( \bullet\)
- \( \Sigma_{\overline{\A}}=\{0,1\}\)
- \( \bullet\)
- \( E_{\overline{\A}}=\{A,B,C,{\color{red} e}\}\)
- \( \bullet\)
- \( I_{\overline{\A}}=\{A,B\}\)
- \( \bullet\)
- \( F_{\overline{\A}}=\{A,C\}\)
- \( \bullet\)
- Fonction de transition :
\begin{eqnarray*}
\tau : E_{\overline{\A}}\times\Sigma_{\overline{\A}} &\longrightarrow& E_{\overline{\A}}\\
(A,0)&\longmapsto& B\\
(A,1)&\longmapsto& C\\
(B,0)&\longmapsto& B\\
(B,1)&\longmapsto& {\color{red} e}\\
(C,0)&\longmapsto& {\color{red} e}\\
(C,1)&\longmapsto& A\\
({\color{red} e},0)&\longmapsto& {\color{red} e}\\
({\color{red} e},1)&\longmapsto& {\color{red} e}
\end{eqnarray*}
\[
M_{\overline{\A}}=\begin{array}{c|cc}
&0&1\\\hline
A&B&{\color{red} e}\\
B&B&C\\
C&{\color{red} e}&A\\
{\color{red} e}&{\color{red} e}&{\color{red} e}
\end{array}
\]
\[\xymatrix@R=1.19cm{
\ar[d]&&\ar[d]&\\
A\ar[d]\ar[rr]^0\ar@/^1pc/@*{[red]}[rrrd]^{\color{red}1}&&B\ar@(rd,ru)[]_0\ar[dl]^1&\\
&C\ar[d]\ar[lu]^1\ar@*{[red]}[rr]_{\color{red}0}&&{\color{red}e}\ar@*{[red]}@(rd,ru)[]_{\color{red} 0,1}\\
&&&
}\]
Exercice
Pour chacun des automates suivants identifier l'alphabet, l'état initiale, les états finaux et donner la représentation sagittale. Compléter l'automate.
- \( \begin{array}{c|*{5}{c}} & a & b \\ \hline A & E & C \\ B \rightarrow & E & A \\ C & C & A \\ D & A & E \\ \rightarrow E & E & B \\ \end{array}\)
- \( \begin{array}{c|*{6}{c}} & u & v \\ \hline A & A & \\ B \rightarrow & & \\ C & B & B \\ D & C & D \\ E & D & \\ \rightarrow F & E & D \\ \end{array}\)
- \( \begin{array}{c|*{5}{c}} & 0 & 1 & 2 \\ \hline A & & D & D \\ B & & D & E \\ \rightarrow C \rightarrow & B & B & E \\ D & D & C & C \\ E & C & D & A \\ \end{array}\)
