Automates
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 ensemble \( I_\A\subset E_\A\) d'états initiaux,
- \( \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\) .
Par exemple, on considère l'ADEF ayant \( \{0,1\}\) comme alphabet, \( \{A,B,C\}\) comme état, \( \{A,B\}\) comme état initiaux, \( \{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 de faire le lien avec le reste de la théorie des graphes.
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'\]
La matrice de l'automate de l'exemple précédent est
\[
M_\A=\begin{array}{c|cc}
&0&1\\\hline
\rightarrow A\rightarrow&B& \\
\rightarrow B \qquad &B&C\\
\qquad C\rightarrow &&A
\end{array}
\]
en précédant (resp. succédant) les états initiaux (resp. finaux) d'une petite flèche.
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.
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]&&\ar[d]\\
A\ar[d]\ar[rr]^0&&B\ar@(rd,ru)[]_0\ar[dl]^1\\
&C\ar[d]\ar[lu]^1&\\
&&
}\)
Automates non déterministes
Définition
Un
automate d'état finis \( \A\) , plus simplement appelé AEF, 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 ensemble \( I_\A\subset E_\A\) d'états initiaux,
- \( \bullet\)
- un ensemble \( F_\A\subset E_\A\) d'états finaux,
- \( \bullet\)
- une fonction de transition \( \tau_\A : E_\A\times \Sigma_\A \longrightarrow \mathcal{P}(E_\A)\) .
La différence entre un ADEF et un AEF est que les passages d'un état à un autre ne sont uniquement déterminés par l'alphabet. Un même caractère peut mener à différents états.
Considérons par exemple l'AEF sur l'alphabet \( \Sigma=\{0,1\}\) ayant comme état \( \{A,B,C\}\) ,
\( \{A\}\) comme état initial, \( \{C\}\) comme état final et ayant pour fonction suivante pour fonction de transition :
\begin{eqnarray*}
\tau : E_\A\times\Sigma_\A &\longrightarrow& \mathcal{P}(E_\A)\\
(A,0)&\longmapsto& \{B,C\}\\
(B,0)&\longmapsto& \{B\}\\
(B,1)&\longmapsto& \{A,C\}\\
(C,1)&\longmapsto& \{C\}
\end{eqnarray*}
De la même manière on représente un automate de deux manières : matricielle et sagittale.
Dans notre exemple nous avons :
\[
M_\A=\begin{array}{c|cc}
&0&1\\\hline
\rightarrow A&B,C& \\
\qquad B \qquad &B&A,C\\
\qquad C\rightarrow &&C
\end{array}
\]
\[\xymatrix{
\ar[d]&& \\
A\ar[rd]_0\ar@/^1pc/[rr]^0&&B\ar@/^1pc/[ll]^1\ar@(rd,ru)[]_0\ar[ld]^1\\
&C\ar@(rd,ru)[]_1\ar[d]&\\
&&
}\]
Proposition
Tout ADEF est un AEF.
Démonstration
Il suffit de composer la fonction de transition d'un ADEF par le plongement canonique \( X\hookrightarrow \mathcal{P}(X)\) .
Il est également possible de rendre un AEF déterministe.
Proposition [Détermination d'un AEF]
Soit \( \A\) un AEF. Considérons l'automate \( \A_{det}\) défini par les règles suivantes :
- \( \bullet\)
- \( \Sigma_{\A_{det}}=\Sigma_{\A}\)
- \( \bullet\)
- \( E_{\A_{det}}=\mathcal{P}(E_{\A})-\{\varnothing\}\)
- \( \bullet\)
- \( I_{\A_{det}}=\{I_\A\}\)
- \( \bullet\)
- \( F_{\A_{det}}=\left\{X\subset E_\A\Big|\exists f\in F_\A, f\in X\right\}\)
- \( \bullet\)
-
\begin{eqnarray*}
\tau_{\A_{det}} : E_{\A_{det}} \times \Sigma_{\A_{det}} &\longrightarrow & E_{\A_{det}}\\
(X,\sigma)&\longmapsto& \dpl{\bigcup_{x\in X}\tau_\A(x,\sigma)}
\end{eqnarray*}
Alors \( \A_{det}\) est un automate déterministe.
Démonstration
Il suffit de voir que la fonction de transition ainsi défini est bien une fonction ce qui se déduit trivialement de la construction.
Remarque
Si l'AEF est un automate à \( n\) états alors l'ADEF associé a \( 2^n-1\) états. Cet automate est donc exponentiellement plus grand que le premier.
Cependant il conserve un avantage qui sera résumé plus tard à travers le théorème de Rabin-Scott.
L'ADEF correspondant à la détermination d'un AEF possède parfois de nombreux états inaccessibles comme nous pouvons le voir sur l'exemple précédent dont l'ADEF associé est :
\[
\xymatrix{
&&&&&&\\
\{A\}\ar@{{<}-}[u]\ar[rr]^0&&\{B,C\}\ar[u]\ar[rd]_0\ar@/^1pc/[rr]^1&&\{A,C\}\ar[u]\ar@/^1pc/[ll]^0\ar[rr]^1&&\{C\}\ar[u]\ar@(rd,ru)[]_1\\
&&&\{B\}\ar[ru]_1\ar@(ld,rd)[]_0&&&
}
\]
Les ensembles \( \{A,B\}\) et \( \{A,B,C\}\) ne sont pas utilisés.
L'algorithme suivant permet de construire progressivement l'ADEF associé à un AEF.
§
Détermination d'un AEF
Initialiser \( E_{\A_{det}}\) à \( \{I_\A\}\)
Tant que \( E_{\A_{det}}\) contient des éléments non marqué
Sélectionner un élément \( X\) de \( E_{\A_{det}}\) non marqué.
Marquer \( X\) .
Pour chaque \( \sigma\in \Sigma_{\A_{det}}\)
Considérer \( \dpl{X'=\bigcup_{x\in X} \tau_\A(x,\sigma)}.\)
Ajouter \( X'\) à \( E_{\A_{det}}\) si ce n'est pas déjà le cas.
Ajouter un arc entre \( X\) et \( X'\) valué par \( \sigma\) .
Fin Pour
Fin Tant Que
Faisons tourner cet algorithme sur l'AEF
\[\xymatrix{
\ar[d]&& \\
A\ar[rd]_0\ar@/^1pc/[rr]^0&&B\ar@/^1pc/[ll]^1\ar@(rd,ru)[]_0\ar[ld]^1\\
&C\ar@(rd,ru)[]_1\ar[d]&\\
&&
}\]
- Initialisation.
-
\[
\xymatrix{
&&&&&&\\
\{A\}\ar@{{<}-}[u]&&&&&&\\
&&&&&&
}
\]
- On choisis \( \{A\}\) .
- On le marque (en mettant un petit point par exemple).
Pour chaque élément composant cet ensemble (ici uniquement \( A\) ), on construit l'image par \( 0\) par \( \tau_\A\) : \( \{B,C\}\) . Cet ensemble n'existant pas on le rajoute et on met un arc entre \( \{A\}\) et \( \{B,C\}\) valué par \( 0\) . On fait de même pour \( 1\) mais il n'y a pas d'image. On arrive donc à
\[
\xymatrix{
&&&&&&\\
\{A\}_{\bullet}\ar@{{<}-}[u]\ar[rr]^0&&\{B,C\}&&&&\\
&&&&&&
}
\]
- On choisis \( \{B,C\}\) .
- On le marque.
Pour chaque élément composant cet ensemble (à savoir \( B\) et \( C\) ), on construit l'image par \( 0\) par \( \tau_\A\) : \( B\) donne \( B\) et \( C\) ne donne rien. On arrive donc à l'ensemble \( \{B\}\) . Cet ensemble n'existant pas on le rajoute et on met un arc entre \( \{B,C\}\) et \( \{B\}\) valué par \( 0\) . On fait de même pour \( 1\) : \( B\) donne \( A\) et \( C\) et \( C\) donne \( C\) , il s'agit donc de l'ensemble \( \{A,C\}\) . Au final :
\[
\xymatrix{
&&&&&&\\
\{A\}_\bullet\ar@{{<}-}[u]\ar[rr]^0&&\{B,C\}_{\bullet}\ar[rd]_0\ar@/^1pc/[rr]^1&&\{A,C\}\\
&&&\{B\}&&&
}
\]
- On choisis \( \{B\}\) .
- (on aurait également pu choisir \( \{A,C\}\) ). On le marque.
On construit l'image de \( B\) par \( 0\) via \( \tau_\A\) : \( \{B\}\) . Par \( 1\) on arrive \( \{A,C\}\)
\[
\xymatrix{
&&&&&&\\
\{A\}_\bullet\ar@{{<}-}[u]\ar[rr]^0&&\{B,C\}_\bullet\ar[rd]_0\ar@/^1pc/[rr]^1&&\{A,C\}&&\\
&&&\{B\}_\bullet\ar[ru]_1\ar@(ld,rd)[]_0&&&
}
\]
- On choisis \( \{A,C\}\) .
- On le marque.
On construit l'image de \( A\) et \( C\) par \( 0\) via \( \tau_\A\) : \( \{B,C\}\) . Par \( 1\) on arrive \( \{C\}\)
\[
\xymatrix{
&&&&&&\\
\{A\}_\bullet\ar@{{<}-}[u]\ar[rr]^0&&\{B,C\}_\bullet\ar[rd]_0\ar@/^1pc/[rr]^1&&\{A,C\}_\bullet\ar@/^1pc/[ll]^0\ar[rr]^1&&\{C\}\\
&&&\{B\}_\bullet\ar[ru]_1\ar@(ld,rd)[]_0&&&
}
\]
- On choisis \( \{C\}\) .
- On le marque.
L'image de \( C\) par \( 0\) via \( \tau_\A\) n'existe pas et l'image de \( C\) par \( 1\) via \( \tau_\A\) donne \( \{C\}\)
\[
\xymatrix{
&&&&&&\\
\{A\}_\bullet\ar@{{<}-}[u]\ar[rr]^0&&\{B,C\}_\bullet\ar[rd]_0\ar@/^1pc/[rr]^1&&\{A,C\}_\bullet\ar@/^1pc/[ll]^0\ar[rr]^1&&\{C\}_\bullet\ar@(rd,ru)[]_1\\
&&&\{B\}_\bullet\ar[ru]_1\ar@(ld,rd)[]_0&&&
}
\]
- FIN.
- Tous les sommets sont marqués. C'est fini. On rajoute les états de sortie dès qu'un éléments d'un sommet possède un élément de \( F_\A\) ; ici il n'y a que \( C\) .
\[
\xymatrix{
&&&&&&\\
\{A\}_\bullet\ar@{{<}-}[u]\ar[rr]^0&&\{B,C\}_\bullet\ar[u]\ar[rd]_0\ar@/^1pc/[rr]^1&&\{A,C\}_\bullet\ar[u]\ar@/^1pc/[ll]^0\ar[rr]^1&&\{C\}_\bullet\ar[u]\ar@(rd,ru)[]_1\\
&&&\{B\}_\bullet\ar[ru]_1\ar@(ld,rd)[]_0&&&
}
\]
Complétion
Définition
Un ADEF des appelé complet si sa fonction de transition est une application.
Par 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}\) .
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\ar@*{[red]}[rd]^{\color{red}1}&\\
&C\ar[d]\ar[lu]^1\ar@*{[red]}[rr]_{\color{red}0}&&{\color{red}e}\ar@*{[red]}@(rd,ru)[]_{\color{red} 0,1}\\
&&&
}\]
Reconnaitre un langage
Définition
Soient \( \A\) un AEF, \( \sigma\in\Sigma_\A^*\) tel que \( \norm{\sigma}=n\) . On dira que \( \sigma\) est
accepté par \( \A\) si il existe une suite \( e_0, e_1, \dots, e_n\) de \( E_\A\) tel que
- \( e_0\in I_\A\) ,
- \( e_n\in F_\A\) ,
- \( \forall k\in [\![1,n]\!], \ \tau_\A(e_{k-1},\sigma_k)=e_{k}\)
Autrement dit : un mot de longueur \( n\) est accepté par un automate s'il existe un chaine de longueur \( n-1\) dans le graphe représentant l'automate ayant un état initial pour origine et un état final pour aboutissement.
\[\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\\
&
}
\]
Les mots \( \varepsilon\) , \( 001\) , \( 100\) , \( 1100\) , \( 010\) sont acceptés par l'automate ci-contre.
Définition
Le langage d'un AEF \( \A\) est l'ensemble des mots acceptés.
\[L(\A)=\left\{\sigma\in\Sigma_\A^*\Big| \sigma \text{ est accepté par }\A\right\}\]
\[\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\\
&
}
\]
Les mots reconnus par cet automate sont tous les mots de \( \{0,1\}\) possédant un nombre paire de \( 0\) .
Définition
Soient \( \Sigma\) un alphabet et \( L(\Sigma)\subset \Sigma^*\) un langage. On dira que \( L(\Sigma)\) est un langage d'états finis, s'il existe un ADEF \( \A\) tel que \( \Sigma=\Sigma_\A\) et \( L(\A)=L(\Sigma)\) . On dit que l'automate \( \A\) reconnait le langage \( L(\Sigma)\) .
Considérons par exemple l'alphabet \( \Sigma=\{0,1,2,3,4,5,6,7,8,9\}\) et le langage \( L(\Sigma)=\N\) des nombres. Il s'agit d'un langage d'états finis. En effet les nombres (ne commençant pas par \( 0\) sauf \( 0\) lui même) sont reconnus par l'A(D)EF suivant :
\[
\xymatrix@C=3cm{
&\ar[d]&\\
&\varnothing\ar[rd]^0\ar[ld]_{1,\dots,9}&\\
Vrai\ar[d]\ar@(ld,lu)[]^\Sigma&Faux\ar@(ld,rd)[]_\Sigma&0\ar[d]\ar[l]^\Sigma\\
&&\\
}
\]
Théorème [Rabin-Scott]
Soit \( \A\) un AEF.
\[L(\A)=L(\A_{det})\]
Il est parfois plus naturel de construire une AEF qui traduit un langage puis de le déterminer (et le compléter) pour pouvoir le programmer.
Considérons par exemple, l'AEF qui reconnait les mots de l'alphabet \( \Sigma=\{a,b\}\) qui se termine par \( bab\) :
\[
\xymatrix{
\ar[r]&
0\ar[r]^b\ar@(lu,ru)[]^a\ar@(ld,rd)[]_b&
1\ar[r]^a&
2\ar[r]^b&
3\ar[r]
&}
\]
Le déterminé (complété) de cet AEF est
\[
\xymatrix{
\ar[r]&
A\ar[r]^b\ar@(lu,ru)[]_a&
B\ar[r]^a\ar@(lu,ru)[]_b&
C\ar@/^1pc/[r]^b\ar@/_2pc/[ll]_a&
D\ar[r]\ar@/^2pc/[ll]^b\ar@/^1pc/[l]_a&
&}
\]
