Automate fini non déterministe

Un automate fini (on dit parfois, par une traduction littérale de l'anglais, machine à états finis, au lieu de machine avec un nombre fini d'états ou machine à états finie ou machine finie à états), finite-state automaton ou finite-state machine (FSA, FSM), est une machine abstraite qui est un outil fondamental en mathématiques discrètes et en informatique. On les retrouve dans la modélisation de processus, le contrôle de processus, les protocoles de communication, la vérification de programmes, la théorie de la calculabilité, dans l'étude des langages formels et en compilation. Ils sont utilisés dans la recherche des motifs dans un texte. Par défaut une machine à états finis est non déterministe.

Notions

Les automates finis (déterministes ou non) reconnaissent exactement des langages rationnels. Ce sont les machines les plus simples dans la hiérarchie de Chomsky, et par conséquent ils sont moins puissants que les automates à pile et, bien entendu, que les machines de Turing.

Fig. 1 : Automate fini déterministe reconnaissant les écritures binaires des multiples de 3.

Un automate est constitué d'états stables et de transitions. Son comportement est dirigé par un mot machine fourni en entrée : l'automate passe d'état en état, suivant les transitions, à la lecture de chaque lettre de l'entrée. Dans l'exemple ci-contre, pour l'entrée $1010010$, et si l'automate démarre en $s_{0}$, il passe successivement par les états $s_{0},s_{1},s_{2},s_{2},s_{1},s_{2},s_{2},s_{1}$, le calcul correspondant est :

$s_{0}{\xrightarrow {1}}s_{1}{\xrightarrow {0}}s_{2}{\xrightarrow {1}}s_{2}{\xrightarrow {0}}s_{1}{\xrightarrow {0}}s_{2}{\xrightarrow {1}}s_{2}{\xrightarrow {0}}s_{1}$.

Table de transition

${\begin{array}{c|cc}&0&1\\\hline s_{0}&s_{0}&s_{1}\\s_{1}&s_{2}&s_{0}\\s_{2}&s_{1}&s_{2}\end{array}}$

L'automate est dit « fini » car il possède un nombre fini d'états : il ne dispose donc que d'une mémoire bornée. On peut très bien considérer des automates sans limitation sur le nombre d'états : la théorie qui en résulte est très analogue à la théorie habituelle. Un automate fini peut être vu comme un graphe orienté étiqueté : les états sont les sommets et les transitions sont les arêtes étiquetées. L'état initial est marqué par une flèche entrante ; un état final est, selon les auteurs, soit doublement cerclé (dans la figure 1 ci-dessus, l'état $s_{0}$ est à la fois initial et final), soit marqué d'une flèche sortante (dans la figure 2 ci-dessous, 1 est initial et 3 est final).

Une autre façon commode de représenter un automate fini est sa table de transition. Elle donne, pour chaque état et chaque lettre, l'état d'arrivée de la transition. Voici à droite la table de transition de l'automate de la figure 1 :

On distinguera les automates finis non déterministes (abrégés en AFN) en anglais non-deterministic finite automata ou NFA, des automates finis déterministes (abrégés en AFD) en anglais deterministic finite automata ou DFA. Un automate est déterministe si, pour chacun de ses états, il y a au plus une transition pour chaque étiquette possible et si, de plus, il a un seul état initial. S'il a exactement une transition par étiquette, on parle alors d'automate déterministe complet. L'automate ci-dessus est déterministe et complet.

Sans précision supplémentaire, un automate fini est toujours non déterministe, mais on devrait plutôt dire « indéterministe », puisqu'il est indifférent qu'il soit déterministe ou non.

Types

Il existe plusieurs types d'automates finis. Les « accepteurs » ou « reconnaisseurs » produisent en sortie une réponse « oui » ou « non », selon qu'ils acceptent (oui) ou rejettent (non) le mot présenté en entrée. Dans l'exemple ci-dessus (Fig. 1), le mot $1010010$ n'est pas accepté, mais le mot $10100101$ est accepté. D'autres automates classent l'entrée par catégorie : au lieu de répondre par oui ou par non, ils répondent par une classification ; de tels automates se rencontrent par exemple en linguistique. Les automates pondérés (weighted automata en anglais) associent à chaque mot une valeur numérique.

Les automates finis servent à caractériser des langages (c'est-à-dire des ensembles, finis ou non, de mots finis en général) : ce sont les langages composés des mots acceptés, ou langages reconnus par les automates. Des extensions des automates finis reconnaissent des langages de mots infinis. Ce sont les automates sur les mots infinis — mots déclencheurs qui se constituent pendant le processus —. Les plus connus d'entre eux sont les automates de Büchi), les automates de Muller. D'autres automates reconnaissent divers types d'arbres (automates d'arbres).

Dans les automates non déterministes, il peut y avoir plusieurs transitions à partir d'un état donné pour une étiquette donnée. Ici, le terme « non déterministe » ne signifie pas la négation de « déterministe » (c'est-à-dire « nécessairement non déterministe ») mais l'absence éventuelle de cette propriété (c'est-à-dire « non nécessairement déterministe »).

Il est remarquable que tout automate fini peut être transformé, au moyen d'une opération qui peut éventuellement augmenter exponentiellement son nombre d'états, en un automate déterministe : c'est la déterminisation expliquée plus loin.

Les automates finis se rencontrent, dans une formulations proche, dans les circuits intégrés numériques, où l'entrée, l'état et le résultat sont des vecteurs de taille fixe de bits. Les machines de Moore et machines de Mealy sont des automates finis avec sortie. Dans les machines de Moore, les actions sont liées aux états, tandis que dans les machines de Mealy les actions (sorties) sont liées aux transitions. Les transducteurs finis sont plus généraux comme automates avec sortie.

Définitions formelles

Alphabet

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

Mot

Un mot sur un alphabet $A$ est une suite finie d'éléments de $A$. Un mot est noté par la juxtaposition de ses lettres. Ainsi, on écrit $u=a_{1}\cdots a_{n}$ au lieu de $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 $\varepsilon$, est appelée le mot vide. L'ensemble des mots sur $A$ est noté $A^{*}$. La concaténation de deux mots $u=a_{1}\cdots a_{n}$ et $v=b_{1}\cdots b_{n}$ est le mot $uv=a_{1}\cdots a_{n}b_{1}\cdots b_{n}$ obtenu par juxtaposition. En particulier, $u\varepsilon =\varepsilon u=u$. La concaténation est associative, et par conséquent $A^{*}$ est un monoïde.

Automate fini

Fig. 2 : Automate reconnaissant les mots finissant par $ab$.

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

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

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

$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 $p_{0}$, son étiquette est le mot $a_{1}a_{2}\cdots a_{n}$ et son état d'arrivée est $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 $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 ${\mathcal {A}}$ est dénoté généralement par $L({\mathcal {A}})$.

Automate complet, automate émondé

• Un automate est complet si pour tout état $q$, et pour toute lettre $a$, il existe au moins une transition partant de $q$ et portant l'étiquette $a$.
• Un état $q$ est accessible s'il existe un chemin d'un état initial à $q$.
• Un état $q$ est coaccessible s'il existe un chemin de $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.

Automate fini déterministe

Fig. 3 : Automate reconnaissant les mots commençant par $ab$.

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

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

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

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

Variations de notations

Il est d'usage de remplacer la notation $\delta$ par un simple point. On écrit alors $q\cdot w$ à la place de $\delta (q,w)$, et la formule $\delta (q,wa)=\delta (\delta (q,w),a)$ devient $q\cdot wa=q\cdot w\cdot a$. Ceci montre aussi que la fonction de transition est une action du monoïde libre $A^{*}$ sur l'ensemble $Q$. On rencontre aussi la notation ${\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 $1$, et il possède un seul état final, l'état $3$. Il reconnaît le langage $abA^{*}$ sur l'alphabet $A=\{a,b\}$.

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

${\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.

Exemples

• L'automate du début de l'article reconnaît les écritures binaire des entiers naturels multiples de 3. Par exemple, le nombre 18, dont l'écriture binaire est $10010$, est reconnu : le calcul est
          $s_{0}{\xrightarrow {1}}s_{1}{\xrightarrow {0}}s_{2}{\xrightarrow {0}}s_{1}{\xrightarrow {1}}s_{0}{\xrightarrow {0}}s_{0}$.
  On peut se convaincre qu'un entier $n$ mène, depuis l'état initial, à $s_{0}$, $s_{1}$ ou $s_{2}$, selon que le reste de sa division par 3 est 0, 1, ou 2.

Automate reconnaissant les mots contenant un nombre impair de lettres $a$.

• L'exemple suivant décrit un automate fini déterministe complet sur l'alphabet binaire $a,b$, qui détermine si l'entrée contient un nombre impair de $a$. Cet automate intervient dans la suite de Thue-Morse. L'automate est ${\mathcal {A}}=(Q,1,\{2\})$, avec $Q=\{1,2\}$, et la fonction de transition donnée par la table :
         ${\begin{array}{c|cc}&a&b\\\hline 1&2&1\\2&1&2\end{array}}$
  Chaque fois que l'on change d'état, la parité du nombre de $a$ change.

Extensions des automates finis (dont epsilon transitions)

Il existe plusieurs généralisation des automates finis, selon la nature des étiquettes que l'on autorise sur les transitions. Un automate asynchrone est un automate où l'étiquette d'une transition peut être le mot vide. Un telle transition est appelée une $\varepsilon$-transition ou transition spontanée, et on parle parfois d'automate à $\varepsilon$-transition. D'autres généralisations autorisent, comme étiquettes, des mots composés de plusieurs lettres. Enfin, une généralisation encore plus large permet comme étiquettes des langages rationnels, représentés par des expressions régulières. Toutes ces extensions n'augmentent pas la puissance des automates finis : un langage reconnu par une quelconque de ces extensions est reconnaissable par un automate fini, et même par un automate fini déterministe.

Fig. 6 : Automate asynchrone reconnaissant $a^{*}b^{*}$.

Fig. 7 : Automate synchronisé reconnaissant $a^{*}b^{*}$.

Un automate asynchrone est un automate fini autorisé à posséder des transitions étiquetées par le mot vide, appelées des $\varepsilon$-transitions. L'automate de la figure 6 est asynchrone.

L'élimination des $\varepsilon$-transitions se fait par un algorithme de fermeture transitive comme suit :

• pour chaque chemin d'un état $s$ à un état $t$ formé de $\varepsilon$-transitions, et pour chaque transition de $t$ à un état $u$ portant une lettre $a$, ajouter une transition de $s$ à $u$ d'étiquette $a$ ;
• pour chaque chemin d'un état $s$ à un état $t$ terminal formé de $\varepsilon$-transitions, ajouter $s$ à l'ensemble des états terminaux ;
• supprimer les $\varepsilon$-transitions.

Dans l'exemple de la figure 6, on ajoute la transition $1{\xrightarrow {b}}2$ dans la première étape, et on déclare que $1$ est état final dans la deuxième étape. On obtient l'automate de la figure 7.

Opérations sur les automates

Déterminisation d'un automate fini

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

Théorème — Pour tout automate fini ${\mathcal {A}}$, il existe un automate fini déterministe ${\mathcal {A'}}$ reconnaissant le même langage.

Fig. 4 : Automate déterminisé des mots se terminant par $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 ${\mathcal {A}}=(Q,{\mathcal {F}},I,T)$ un automate fini sur un alphabet $A$.

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

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

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

L'automate ${\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 $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.

Union, étoile etc.

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

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

Produit direct et intersection

Soient ${\mathcal {A_{1}}}=(Q_{1},{\mathcal {F_{1}}},I_{1},T_{1})$ et ${\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

${\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 ${\mathcal {G}}$ sont les triplets

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

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

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

Le théorème de Kleene

Le mathématicien Stephen C. Kleene a démontré que les langages reconnus par les automates finis sont exactement les langages qui peuvent être décrits par les expressions rationnelles. De manière plus concise, il y a égalité entre la famille des langages rationnels et la famille des langages reconnaissables sur un alphabet fini donné.

De plus, la démarche est constructive : pour toute expression rationnelle, on peut construire un automate fini (déterministe ou non) qui reconnaisse cette expression ; de même, pour tout automate fini (déterministe ou non), on peut exprimer sous forme d'une expression rationnelle le langage qu'il reconnaît.

Expressions rationnelles et langages rationnels

Les expressions rationnelles, ou expressions régulières sont des expressions qui décrivent les langages rationnels. Le terme expression régulière est antérieur, et les langages décrits par ces expressions sont naturellement aussi appelés langages réguliers.

Les expressions rationnelles, plus ou moins étendues, servent notamment à la recherche de motifs dans un texte.

Une expression rationnelle $E$ sur un alphabet $A$ est soit :

• un symbole dénotant l'ensemble vide ;
• un symbole dénotant le mot vide : $\epsilon$ ou $1$ ;
• une lettre $a$ de l'alphabet $A$ ;
• une réunion (ou somme, en notation algébrique) de deux expressions rationnelles $M$ et $N$, notée $E=M|N$ ou $E=M+N$
• une concaténation (ou un produit, en notation algébrique) de deux expressions rationnelles $M$ et $N$, notée $E=M\cdot N$ ou simplement $E=MN$
• une répétition, ou étoile, ou itération, d'une expression rationnelle $M$ notée $E=M^{*}$.

On distingue soigneusement l'expression rationnelle, qui est une simple expression, c'est-à-dire une chaîne de caractères qui représente un arbre d'expression, du langage que représente cette expression appelé le langage dénoté par l'expression. Ce langage est noté $L(E)$ et est défini récursivement, à partir de l'expression :

• $L(\emptyset )=\emptyset$
• $L(\varepsilon )=L(1)=\{\varepsilon \}$
• $L(X|Y)=L(X+Y)=L(X)\cup L(Y)$
• $L(X\cdot Y)=L(XY)=L(X)L(Y)$
• $L(X^{*})=L(X)^{*}$

Par exemple,

$L[(a+b)^{*}(a+\varepsilon )(a+b)^{*}]=\{a,b\}^{*}\{a,\varepsilon \}\{a,b\}^{*}$

Des expressions aux automates

Automate pour l'ensemble vide, le mot vide et une lettre.

Automate pour l'union.

Il existe plusieurs méthodes pour construire un automate fini à partir d'une expression rationnelle

Automate pour le produit.

Automate pour l'étoile.

Automate obtenu par la méthode de Thompson pour l'expression $(a+b)^{*}b(a+\epsilon )(a+b)^{*}$.

Méthode de Thompson

La méthode de Thompson 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 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 pousse plus loin encore l'élimination des epsilon-transitions.

Méthode de Glushkov

La méthode de Glushkov 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é que l'automate de Glushkov est le même que l'automate obtenu en supprimant les $\varepsilon$-transitions de l'automate de Thompson.

Méthode des dérivées

La méthode des quotients ou résiduels ou dérivées, est due à Brzozowski 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 $+$.

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.

Des automates aux expressions

Il existe plusieurs algorithmes pour calculer, à partir d'un automate fini donné par son graphe, une expression rationnelle qui le représente. Ces algorithmes opèrent tous par réduction, en éliminant les états progressivement. La mise-en-œuvre diffère, selon que l'on traite les opérations successivement, comme la méthode de résolution des systèmes d'équations linéaires par la méthode de Gauss, ou récursivement par partition en blocs, comme la méthode de Conway. Une difficulté réside dans le fait que, selon le mode opératoire, le résultat ne donne pas la même expression, mais seulement des expressions équivalentes, donc des expressions différentes dénotant le même langage.

Systèmes d'équations linéaires

Fig. 7 : Un automate reconnaissant $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, et qui est fréquemment appelé méthode d'élimination des variables. L'ingrédient de base est ce qu'on appelle le lemme d'Arden.

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

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

où

$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 $L_{q}$ des $n$ équations de la forme précédente, et d'obtenir une expression explicite des $L_{q}$ et notamment des $L_{i},i\in I$, ce qui détermine le langage reconnu par l'automate ${\mathcal {A}}$.

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

${\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 :

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

En reportant dans la première, on obtient :

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

et le lemme d'Arden donne :

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

Note : Les ensembles $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.

Méthode de Conway

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.

Méthode de Brzozowski et McCluskey

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.

Complexité en taille des opérations

Les opérations de passage d'une expression à l’automate et réciproquement ont une complexité en temps et en place qu'il est important de savoir évaluer, en théorie et pour les applications. Un article de Hermann Gruber et Markus Holzer en fait un tour d'horizon. La mesure de la complexité d'un automate peut se faire en comptant le nombre d'états ou le nombre de transitions.

Pour un langage rationnel L sur un alphabet A, on note :

• sc(L) le nombre minimal d'états dans un automate fini déterministe ;
• tc(L) le nombre minimal de transitions dans un automate fini déterministe ;
• nsc(L) le nombre minimal d'états dans un automate fini non déterministe ;
• ntc(L) le nombre minimal de transitions dans un automate fini non déterministe.

Pour un automate acceptant L. Les deux dernières mesures de complexité peuvent être indicées par ε, indiquant que l'on autorise les epsilon transitions. On a les inégalités suivantes, où |A| est la taille de l'alphabet :

• $\operatorname {nsc} _{\varepsilon }(L)=\operatorname {nsc} (L)\leq \operatorname {sc} (L)\leq 2^{\operatorname {nsc} (L)}$,
• $\operatorname {tc} (L)=|A|\operatorname {sc} (L)$,
• $\operatorname {nsc} (L)-1\leq \operatorname {ntc} _{\varepsilon }(L)\leq \operatorname {ntc} (L)\leq |A|(\operatorname {nsc} (L))^{2}$

Pour les expressions régulières, il y a plusieurs façons de les mesurer, selon que l'on compte le nombre de symboles de lettres, de lettres et symboles d'opération, ou lettres, symboles d'opération et parenthèses. On a les inégalités suivantes :

• $\operatorname {taille} (L)\leq 3{\cdot }\operatorname {pn} (L)$ et $\operatorname {taille} (L)\leq 8\cdot \operatorname {largeur} (L)-3$
• $\operatorname {largeur} (L)\leq 1/2\ (\operatorname {taille} (L)+1)$ et $\operatorname {largeur} (L)\leq 1/2\ (\operatorname {pn} (L)+1)$
• $\operatorname {pn} (L)\leq 1/2(\operatorname {taille} (L)+1)$ et $\operatorname {pn} (L)\leq 4\cdot \operatorname {taille} (L)-1$

Ici la « taille » est le nombre total de symboles, y compris les lettres, opérations, parenthèses d'une expression, « pn » est le nombre de symboles sans les parenthèses, donc juste de lettres et symboles d’opérations (« pn » pour « polish notation »), et « largeur » est nombre total d’occurrences de lettres, donc sans les symboles d’opérations.

Grammaires et les langages rationnels

Les langages rationnels forment la classe la plus simple de la hiérarchie de Chomsky et sont, à ce titre, engendrés par des grammaires algébriques particulières, les grammaires linéaires droites ou grammaires linéaires gauches. Ce sont des grammaires où toutes les règles sont de la forme $X\to w$ ou $X\to wY$, avec $w$ un mot ne contenant pas de variable et $X,Y$ des variables. (Pour les grammaires linéaire gauches, remplacer $X\to wY$ par $X\to Yw$.)

On construit, pour une grammaire linéaire droite $G=(V,S,P)$, un automate fini (généralisé, avec des mots comme étiquettes) comme suit : les états de l'automate sont les variables de la grammaire, plus un état spécial $f$. L'état initial est $S$, le seul état final est $f$. Chaque règle $X\to wY$ fournit une transition $(X,w,Y)$ de $X$ vers $Y$ d'étiquette $w$, et chaque règle $X\to w$ fournit une transition $(X,w,f)$ de $X$ vers $f$ d'étiquette $w$.

Minimisation d'un automate fini

Deux automates finis sont équivalents s'ils reconnaissent le même langage. C'est un résultat remarquable de la théorie qu'il existe, pour tout automate fini, un seul automate fini déterministe minimal (c'est-à-dire ayant un nombre minimal d'état) qui est équivalent à l'automate donné. De plus, cet automate, appelé automate minimal, se calcule efficacement par l'algorithme de Moore ou l'algorithme de Hopcroft. L'unicité de l'automate ayant un nombre minimal d'état n'est plus vraie pour les automates non déterministes.

On peut ainsi décider de l'équivalence de deux automates en calculant, pour chacun, l'automate minimal déterministe correspondant, et en testant l'égalité des deux automates obtenus.

Monoïde de transition et monoïde syntaxique

Soit ${\mathcal {A}}=(Q,i,T)$ un automate fini déterministe complet sur un alphabet $A$. Chaque mot $w$ définit une application $\sigma (w):Q\to Q$ donnée par

$q\sigma (w)=q\cdot w$

Ici l'argument de la fonction est noté à gauche de la fonction. On a

$\sigma (xy)=\sigma (x)\sigma (y)$

En effet $q\sigma (xy)=q\cdot xy=q\cdot x\cdot y=(q\sigma (x))\cdot y=(q\sigma (x))\sigma (y)$. L'application $\sigma :A^{*}\to Q^{Q}$ est donc un morphisme de $A^{*}$ dans le monoïde des applications de $Q$ dans lui-même. L'image $\sigma (A^{*})$ est appelée le monoïde de transition de l'automate. Lorsque l'automate est minimal, le monoïde de transition est isomorphe au monoïde syntaxique du langage reconnu par l'automate.

Mise en œuvre

Un automate fini peut être représenté en utilisant une table de transition d'état. On le représente alors sous forme logicielle avec une matrice de transition d'état. Dans certains cas, il est plus avantageux d'utiliser une matrice creuse, ou un énorme switch qui distribue selon les états, et pour chaque état un autre switchs qui distingue les symboles d'entrée.

La réalisation d'automates finis se fait aussi, sous forme matérielle, par un dispositif de logique programmable appelé table logique programmable (en).

Voir aussi

Articles connexes

• 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

Bibliographie

• 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).

Références historiques

• 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)

Liens externes

• 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