Automate fini non déterministe

Un alphabet est un ensemble, en général supposé fini et non vide. Ses éléments sont des lettres.

Un mot sur un alphabet ${\displaystyle A}$ est une suite finie d'éléments de ${\displaystyle A}$. Un mot est noté par la juxtaposition de ses lettres. Ainsi, on écrit ${\displaystyle u=a_{1}\cdots a_{n}}$ au lieu de ${\displaystyle u=(a_{1},\ldots ,a_{n})}$. La longueur d'un mot est le nombre d'éléments qui le composent. La suite vide, mot de longueur 0, souvent notée ${\displaystyle \varepsilon }$, est appelée le mot vide. L'ensemble des mots sur ${\displaystyle A}$ est noté ${\displaystyle A^{*}}$. La concaténation de deux mots ${\displaystyle u=a_{1}\cdots a_{n}}$ et ${\displaystyle v=b_{1}\cdots b_{n}}$ est le mot ${\displaystyle uv=a_{1}\cdots a_{n}b_{1}\cdots b_{n}}$ obtenu par juxtaposition. En particulier, ${\displaystyle u\varepsilon =\varepsilon u=u}$. La concaténation est associative, et par conséquent ${\displaystyle A^{*}}$ est un monoïde.

Fig. 2 : Automate reconnaissant les mots finissant par ${\displaystyle ab}$.

Un automate fini ou automate fini non déterministe (AFN) ${\displaystyle {\mathcal {A}}}$ sur un alphabet ${\displaystyle A}$ est un quadruplet ${\displaystyle {\mathcal {A}}=(Q,{\mathcal {F}},I,T)}$, où :

• ${\displaystyle Q}$ est un ensemble fini d'états,
• ${\displaystyle {\mathcal {F}}\subset Q\times A\times Q}$ est l'ensemble des transitions,
• ${\displaystyle I\subseteq Q}$ est l'ensemble des états initiaux,
• et ${\displaystyle T\subseteq Q}$ est un ensemble d'états finaux ou terminaux.

Une transition ${\displaystyle f=(p,a,q)}$ est composée d'un état de départ ${\displaystyle p}$, d'une étiquette ${\displaystyle a}$ et d'un état d'arrivée ${\displaystyle q}$. Un calcul ${\displaystyle c}$ (on dit aussi un chemin ou une trace) est une suite de transitions consécutives :

${\displaystyle c=(p_{0},a_{1},p_{1})(p_{1},a_{2},p_{2})\cdots (p_{n-1},a_{n},p_{n})}$

Son état de départ est ${\displaystyle p_{0}}$, son étiquette est le mot ${\displaystyle a_{1}a_{2}\cdots a_{n}}$ et son état d'arrivée est ${\displaystyle p_{n}}$. Un calcul est réussi si son état de départ est un des états initiaux, et son état d'arrivée est un des états terminaux.

Un mot ${\displaystyle w}$ est reconnu ou accepté par l'automate s'il est l'étiquette d'un calcul réussi. Le langage reconnu par l'automate est l'ensemble des mots reconnus. Un langage est reconnaissable s'il est reconnu par un automate fini.

Le langage reconnu par un automate ${\displaystyle {\mathcal {A}}}$ est dénoté généralement par ${\displaystyle L({\mathcal {A}})}$.

• Un automate est complet si pour tout état ${\displaystyle q}$, et pour toute lettre ${\displaystyle a}$, il existe au moins une transition partant de ${\displaystyle q}$ et portant l'étiquette ${\displaystyle a}$.
• Un état ${\displaystyle q}$ est accessible s'il existe un chemin d'un état initial à ${\displaystyle q}$.
• Un état ${\displaystyle q}$ est coaccessible s'il existe un chemin de ${\displaystyle q}$ à un état final.
• Un automate est accessible (coaccessible) si tous ses états sont accessibles (coaccessibles).
• Un automate est émondé si tous ses états sont à la fois accessibles et coaccessibles.

Fig. 3 : Automate reconnaissant les mots commençant par ${\displaystyle ab}$.

Un automate fini déterministe (AFD) ${\displaystyle {\mathcal {A}}}$ sur un alphabet ${\displaystyle A}$ est un automate fini qui vérifie les deux conditions suivantes :

• il possède un seul état initial ;
• pour tout état ${\displaystyle q}$, et pour toute lettre ${\displaystyle a}$, il existe au plus une transition partant de ${\displaystyle q}$ et portant l'étiquette ${\displaystyle a}$.

Pour un automate déterministe, la fonction de transition ${\displaystyle \delta :Q\times A\to Q}$ est la fonction partielle définie par : ${\displaystyle \delta (q,a)=q'}$ si ${\displaystyle (q,a,q')}$ est une transition. Si la fonction de transition est partout définie, l'automate est complet. La fonction de transition ${\displaystyle \delta }$ est étendue en une application (partielle) ${\displaystyle Q\times A^{*}\to Q}$ en posant

• ${\displaystyle \delta (q,\varepsilon )=q}$ pour tout état ${\displaystyle q}$. Ici ${\displaystyle \varepsilon }$ dénote le mot vide.
• ${\displaystyle \delta (q,wa)=\delta (\delta (q,w),a)}$ pour tout état ${\displaystyle q}$, tout mot ${\displaystyle w}$ et toute lettre ${\displaystyle a}$.

Il est d'usage de remplacer la notation ${\displaystyle \delta }$ par un simple point. On écrit alors ${\displaystyle q\cdot w}$ à la place de ${\displaystyle \delta (q,w)}$, et la formule ${\displaystyle \delta (q,wa)=\delta (\delta (q,w),a)}$ devient ${\displaystyle q\cdot wa=q\cdot w\cdot a}$. Ceci montre aussi que la fonction de transition est une action du monoïde libre ${\displaystyle A^{*}}$ sur l'ensemble ${\displaystyle Q}$. On rencontre aussi la notation ${\displaystyle {\mathcal {A}}=(Q,i,T)}$ pour un automate déterministe, la fonction de transition étant sous-entendue (comme la loi de composition dans un groupe, par exemple). L'automate de la figure 3 est déterministe et incomplet. Son état initial est ${\displaystyle 1}$, et il possède un seul état final, l'état ${\displaystyle 3}$. Il reconnaît le langage ${\displaystyle abA^{*}}$ sur l'alphabet ${\displaystyle A=\{a,b\}}$.

On rencontre dans la littérature l'écriture d'un automate fini général sous forme de quintuplet

${\displaystyle {\mathcal {A}}=(Q,{\mathcal {F}},I,T,A)}$ .

Ici, l'alphabet de l'automate est inclus dans la spécification. La même façon d'inclure alphabet de définition dans la spécification se voit aussi pour les automates déterministes.

Il est toujours possible, à partir d'un automate fini non déterministe ${\displaystyle {\mathcal {A}}}$, de construire un automate fini déterministe ${\displaystyle {\mathcal {A'}}}$ reconnaissant le même langage :

Fig. 4 : Automate déterminisé des mots se terminant par ${\displaystyle ab}$.

Fig. 5 : Automate déterminisé et émondé.

La méthode de construction est appelée la construction par sous-ensembles en français, et powerset construction en anglais.

Soit ${\displaystyle {\mathcal {A}}=(Q,{\mathcal {F}},I,T)}$ un automate fini sur un alphabet ${\displaystyle A}$.

On construit l'automate ${\displaystyle {\mathcal {A'}}}$ comme suit :

• l'ensemble d'états de ${\displaystyle {\mathcal {A'}}}$ est l'ensemble ${\displaystyle P=2^{Q}}$ des parties de l'ensemble ${\displaystyle Q}$ ;
• l'état initial de ${\displaystyle {\mathcal {A'}}}$ est ${\displaystyle I}$ ;
• les états terminaux de ${\displaystyle {\mathcal {A'}}}$ sont les parties ${\displaystyle T'}$ de ${\displaystyle Q}$ qui ont une intersection non vide avec ${\displaystyle T}$ ;
• la fonction de transition de ${\displaystyle {\mathcal {A'}}}$ est définie, pour ${\displaystyle S\subseteq Q}$ et ${\displaystyle a\in A}$, par

${\displaystyle S\cdot a=\{s'\in Q\mid \exists s\in S:(s,a,s')\in {\mathcal {F}}\}}$.

L'automate ${\displaystyle {\mathcal {A'}}}$ est déterministe par construction.

Pour l'exemple de la figure 2, on obtient l'automate de la figure 4. Bien entendu, seuls les quatre états du haut sont utiles et même l'état ${\displaystyle 123}$ peut être supprimé, puisqu'il n'est pas accessible. L'automate accessible déterminisé est celui de la figure 5.

Le nombre d'états de l'automate déterminisé peut être exponentiel par rapport au nombre d'états de l’automate de départ[3]^,[4].

Soit ${\displaystyle {\mathcal {A}}(M)}$ (respectivement ${\displaystyle {\mathcal {A}}(N)}$) l'automate fini reconnaissant le langage dénoté par l'expression rationnelle ${\displaystyle M}$ (respectivement ${\displaystyle N}$). Les constructions sont les suivantes (d'autres constructions existent, évitant l'introduction d'${\displaystyle \varepsilon }$-transitions :

• Automate ${\displaystyle {\mathcal {A}}(M+N)}$ pour la réunion :
  Il suffit de faire la réunion disjointe des automates ${\displaystyle {\mathcal {A}}(M)}$ et ${\displaystyle {\mathcal {A}}(N)}$. Une variante consiste à introduire un nouvel état initial, et des ${\displaystyle \varepsilon }$-transitions de cet état vers les états initiaux des deux automates.
• Automate ${\displaystyle {\mathcal {A}}(M\cdot N)}$ pour le produit :
  L'automate a pour états les états de ${\displaystyle {\mathcal {A}}(M)}$ et de ${\displaystyle {\mathcal {A}}(N)}$. Les états initiaux sont ceux de ${\displaystyle {\mathcal {A}}(M)}$, les terminaux sont ceux de ${\displaystyle {\mathcal {A}}(N)}$. Les transitions sont celles de ${\displaystyle {\mathcal {A}}(M)}$ et de ${\displaystyle {\mathcal {A}}(N)}$, et de plus des ${\displaystyle \varepsilon }$-transitions des états terminaux de ${\displaystyle {\mathcal {A}}(M)}$ vers les états initiaux de ${\displaystyle {\mathcal {A}}(N)}$
• Automate ${\displaystyle {\mathcal {A}}(M^{*})}$ pour l'étoile :
  On part de l'automate ${\displaystyle {\mathcal {A}}(M)}$ que l'on augmente de deux états ${\displaystyle i}$ et ${\displaystyle t}$. On ajoute des ${\displaystyle \varepsilon }$-transitions
  — de ${\displaystyle i}$ à tout état initial de ${\displaystyle {\mathcal {A}}(M)}$
  — de tout état final de ${\displaystyle {\mathcal {A}}(M)}$ à ${\displaystyle t}$
  — de ${\displaystyle i}$ à ${\displaystyle t}$ et de ${\displaystyle t}$ à ${\displaystyle i}$.L'état ${\displaystyle i}$ (resp. ${\displaystyle t}$) est l'état initial (resp. final) de ${\displaystyle {\mathcal {A}}(M^{*})}$.

• Automate transposé On peut aussi construire un automate qui reconnaît les miroirs des mots d'un langage, c'est l'automate transposé ou automate miroir.

Soient ${\displaystyle {\mathcal {A_{1}}}=(Q_{1},{\mathcal {F_{1}}},I_{1},T_{1})}$ et ${\displaystyle {\mathcal {A_{2}}}=(Q_{2},{\mathcal {F_{2}}},I_{2},T_{2})}$ deux automates finis. Le produit direct ou produit cartésien des deux automates est l’automate

${\displaystyle {\mathcal {C}}={\mathcal {A_{1}}}\times {\mathcal {A_{2}}}=(Q_{1}\times Q_{2},{\mathcal {G}},I_{1}\times I_{2},T_{1}\times T_{2})}$,

où les transitions de ${\displaystyle {\mathcal {G}}}$ sont les triplets

${\displaystyle ((p_{1},p_{2}),a,(q_{1},q_{2}))}$,

avec ${\displaystyle (p_{1},a,q_{1})\in {\mathcal {F_{1}}}}$ et ${\displaystyle (p_{2},a,q_{2})\in {\mathcal {F_{1}}}}$.

Le langage reconnu par ${\displaystyle {\mathcal {C}}}$ est l’intersection des langages reconnus par ${\displaystyle {\mathcal {A_{1}}}}$ et ${\displaystyle {\mathcal {A_{2}}}}$. C'est pourquoi on rencontre aussi la notation ${\displaystyle {\mathcal {A_{1}}}\cap {\mathcal {A_{2}}}}$ à la place ${\displaystyle {\mathcal {A_{1}}}\times {\mathcal {A_{2}}}}$.

La méthode de Thompson[5] a été utilisée par Ken Thompson dans l'implémentation de la commande grep du système Unix.
On construit récursivement des automates pour les composants d'une expression. La forme particulière des automates permet de les combiner avec une grande facilité. L'automate obtenu est non déterministe asynchrone.

La construction de Thompson peut être optimisée ; une construction attribuée à Ott et Feinstein[6] introduit les variantes que voici pour minimiser le nombre de epsilon transitions:

• Pour l’union, au lieu d’introduire deux nouveaux états, on fusionne les états initiaux et finaux
• Pour la concaténation, on fusionne l’état final du premier avec l’état initial du second
• Pour l’étoile, un circuit formé uniquement de epsilon transitions est supprimé et les états du circuit fusionnés.

Un automate nommé « follow automaton » et introduit par Ilie et Yu[6] pousse plus loin encore l'élimination des epsilon-transitions.

La méthode de Glushkov[7] est attribuée à l'informaticien Glushkov, permet de construire un automate non déterministe de même taille (nombre d'états) que la taille (nombre de symboles) de l'expression rationnelle.
Il a été observé[8] que l'automate de Glushkov est le même que l'automate obtenu en supprimant les ${\displaystyle \varepsilon }$-transitions de l'automate de Thompson.

La méthode des quotients ou résiduels ou dérivées, est due à Brzozowski[9] On forme les quotients (ou résiduels) successifs de l'expression. Il n'y en a qu'un nombre fini de différents, après application d'un certain nombre de règles de simplification qui sont l'associativité, la commutativité et l'idempotence de l'opération ${\displaystyle +}$.

Aucune de ces méthodes ne donne directement l'automate minimal d'un langage. On peut aussi employer des constructions simples d'automates pour la réunion, le produit et l'étoile de langages, et opérer récursivement.

Fig. 7 : Un automate reconnaissant ${\displaystyle a^{*}b^{*}}$.

À tout automate, on peut associer un système d'équations linéaires dont les coefficients sont des parties de l'alphabet. On résout le système par une méthode similaire à la méthode d'élimination de Gauss[10], et qui est fréquemment appelé méthode d'élimination des variables[8]. L'ingrédient de base est ce qu'on appelle le lemme d'Arden.

Soit ${\displaystyle {\mathcal {A}}=(Q,{\mathcal {F}},I,T)}$ un automate fini sur un alphabet ${\displaystyle A}$. Pour chaque état ${\displaystyle q\in Q}$, soit ${\displaystyle L_{q}}$ le langage reconnu à partir de l'état ${\displaystyle q}$, c'est-à-dire le langage reconnu en prenant ${\displaystyle q}$ pour état initial. On pose enfin ${\displaystyle A_{q,r}=\{a\in A\mid (q,a,r)\in T\}}$. Ce sont les étiquettes des transitions de ${\displaystyle q}$ à ${\displaystyle r}$. On a alors :

${\displaystyle L_{q}=\bigcup _{r\in Q}A_{q,r}\cdot L_{r}\cup F_{q}}$

où

${\displaystyle F_{q}={\begin{cases}\{\varepsilon \}&q\in F\\\varnothing &q\notin F\end{cases}}}$

L'application du lemme d'Arden permet d'éliminer une à une les inconnues ${\displaystyle L_{q}}$ des ${\displaystyle n}$ équations de la forme précédente, et d'obtenir une expression explicite des ${\displaystyle L_{q}}$ et notamment des ${\displaystyle L_{i},i\in I}$, ce qui détermine le langage reconnu par l'automate ${\displaystyle {\mathcal {A}}}$.

Exemple : Reprenons l'automate de la figure 7. Le système associé s'écrit :

${\displaystyle {\begin{array}{lcl}L_{1}&=&aL_{1}\cup bL_{2}\cup \varepsilon \\L_{2}&=&bL_{2}\cup \varepsilon \end{array}}}$

La deuxième équation donne :

${\displaystyle L_{2}=b^{*}}$

En reportant dans la première, on obtient :

${\displaystyle L_{1}=aL_{1}\cup b^{*}}$

et le lemme d'Arden donne :

${\displaystyle L_{1}=a^{*}b^{*}}$

Note : Les ensembles ${\displaystyle A_{q,r}}$ qui, dans les équations ci-dessus sont des parties de l'alphabet, peuvent être remplacés par des ensembles rationnels quelconques : les langages solutions sont toujours rationnels, à condition de prendre la plus petite solution dans le lemme d'Arden.

Une méthode semblable est l'algorithme de Conway. Il opère de manière récursive, au moyen d'une partition en blocs de l’automate. La représentation choisie est matricielle, et la partition en blocs de l'automate se ramène à la partition en blocs de la matrice associée.

Encore une méthode d'élimination, cette méthode utilise de façon intensive la représentation graphique de l'automate. L'automate lui-même est généralisé, en autorisant, comme étiquettes des transitions, non seulement des lettres, mais des expressions régulières. Partant d'une automate fini, on élimine progressivement les états, et à la fin, on se retrouve avec un automate ayant une seule transition. L'étiquette de cette transition est une expression rationnelle pour le langage reconnu par l'automate.

• Théorie des automates
• Automate fini déterministe
• Automate fini inambigu
• Hiérarchie de Chomsky
• Langage rationnel
• Automate à pile
• Automate d'arbres
• Structure de Kripke
• Système de transition d'états

• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)

• Manfred Droste, Werner Kuich et Heiko Vogler, Handbook of Weighted Automata, Springer-Verlag, 2009, 608 p. (ISBN 978-3-642-01491-8)
• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2007, 3^e éd. (ISBN 978-0-32146225-1)
• Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5)
  Traduction anglaise avec corrections : Elements of Automata Theory, Cambridge University Press 2009, (ISBN 9780521844253)
• Patrice Séébold, Théorie des automates : Méthodes et exercices corrigés, Vuibert, 1999, 198 p. (ISBN 978-2-7117-8630-5)
• Hermann Gruber et Markus Holzer, « From Finite Automata to Regular Expressions and Back : A Summary on Descriptional Complexity », Int. J. Found. Comput. Sci., vol. 26, n^o 08,‎ décembre 2015, p. 1009-1040 (DOI 10.1142/s0129054115400110).

• John A. Brzozowski, « Derivatives of regular expressions », J. Assoc. Comput. Mach., vol. 11,‎ 1964, p. 481–494
• Victor M. Glushkov, « The abstract theory of automata », Russian Math. Surveys, vol. 16,‎ 1961, p. 1–53
• Ken Thompson, « Regular expression search algorithm », Comm. Assoc. Comput. Mach., vol. 11,‎ 1968, p. 419–422
• Robert McNaughton et H. Yamada, « Regular expressions and state graphs for automata », IRE Trans. Electronic Computers, vol. EC-9, n^o 1,‎ janvier 1960, p. 39-47 (DOI 10.1109/TEC.1960.5221603)

• L'histoire des automates finis a été décrite par Dominique Perrin dans l'article : Les débuts de la théorie des automates, paru dans Technique et science informatiques 1995, vol. 14, n^o 4, p. 409-433.
• Des outils informatiques permettent de générer des programmes afin de plus facilement définir des automates Hierarchical State Machine Compiler
• FSM: Open Source Finite State Machine Generation in Java by Alexander Sakharov FSM
• SMC: An Open Source State Machine Compiler that generates FSM for many languages as C, Python, Lua, Scala, PHP, Java, VB, etc SMC

• Portail de l'informatique théorique