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 \left(\Sigma_\A\cup\{\varepsilon\}\right) \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.
Exemple
Considérons 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.
Exemple
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@R=0.5cm{
\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
On compose la fonction de transition d'un ADEF par le plongement \( 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
Exemple
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&&&
}
\]
Exercice
Pour chacun des automates suivants, donner une représentation sagittale et construire l'automate déterministe associé.
- \( \begin{array}{|c*{2}{|c}|}\hline&0&1\\\hline A\rightarrow &C&C\\\hline \rightarrow B&A,B,C&B\\\hline C&B,C&A,C\\\hline \end{array}\)
- \( \begin{array}{|c*{2}{|c}|}\hline&0&1\\\hline A\rightarrow &A&C\\\hline B&B,C&A\\\hline \rightarrow C&A,B,C&B\\\hline \end{array}\)
- \( \begin{array}{|c*{2}{|c}|}\hline&0&1\\\hline A&B,C&A\\\hline \rightarrow B&B&A\\\hline C\rightarrow &A&B\\\hline \end{array}\)
- \( \begin{array}{|c*{2}{|c}|}\hline&0&1\\\hline \rightarrow A&B&C\\\hline B&C&C\\\hline C\rightarrow &A&B,C\\\hline \end{array}\)
- \( \begin{array}{|c*{2}{|c}|}\hline&0&1\\\hline \rightarrow A\rightarrow &C&A\\\hline B&C&C\\\hline C&A&A,B\\\hline \end{array}\)
- \( \begin{array}{|c*{2}{|c}|}\hline&0&1\\\hline \rightarrow A&C&B\\\hline B\rightarrow &C&A,C\\\hline C&A&A\\\hline \end{array}\)
- \( \begin{array}{|c*{3}{|c}|}\hline&a&b&c\\\hline A&C&D&D\\\hline B\rightarrow &A,D&A,B,C,D&A,B,D\\\hline C&A,B,C,D&C&A\\\hline \rightarrow D&A&A&A\\\hline \end{array}\)
- \( \begin{array}{|c*{3}{|c}|}\hline&a&b&c\\\hline \rightarrow A\rightarrow &C&A,C,D&D\\\hline B&A,B&C&A,B,C,D\\\hline C&D&C&B,C\\\hline D&B&A,B,D&B\\\hline \end{array}\)
