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) - Wikipedia Orange$ , où:

$Q - Wikipedia Orange$ est un ensemble fini d'états,
$\mathcal{F}\subset Q\times A\times Q - Wikipedia Orange$ est l'ensemble des transitions,
$I \subseteq Q - Wikipedia Orange$ est l'ensemble des état initiaux,
et $T \subseteq Q - Wikipedia Orange$ est un ensemble d'états finals 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 - Wikipedia Orange$ (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) - Wikipedia Orange$

Son état de départ est $p_0$ , son étiquette est le mot $a_1a_2\cdots a_n$ et son état d'arrivée est $p_n - Wikipedia Orange$ . 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 - Wikipedia Orange$ 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}) - Wikipedia Orange$ .

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 - Wikipedia Orange$ .
Un état $q$ est accessible s'il existe un chemin d'un état initial à $q - Wikipedia Orange$ .
Un état $q$ est coaccessible s'il existe un chemin de $q - Wikipedia Orange$ à 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 coacessibles.

Automate fini déterministe

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

Un automate fini déterministe (AFD) $\mathcal{A}$ sur un alphabet $A - Wikipedia Orange$ 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 - Wikipedia Orange$ .

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 - Wikipedia Orange$ en posant

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

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\} - Wikipedia Orange$ .

Extensions des automates finis

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 - Wikipedia Orange$ -transition. D'autres généralisations autorisent, comme étiquettes, des mots composés de plusieurs lettres. Enfin, la généralisation la plus large autorise 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.

Déterminisation d'un automate fini

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

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

Fig. 4 : Automate déterminisé des mots se terminant par $ab - Wikipedia Orange$

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

La méthode de construction est appelée l'algorithme des parties (en) en français, et powerset construction en anglais.

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

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

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

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

L'automate $\mathcal{A'} - Wikipedia Orange$ 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 - Wikipedia Orange$ 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.^[2].

Automates asynchrones

Fig. 6 : Automate asynchrone reconnaissant $a^*b^* - Wikipedia Orange$

Fig. 7 : Automate synchronisé reconnaissant $a^*b^* - Wikipedia Orange$

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

L'élimination des $\varepsilon - Wikipedia Orange$ -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 - Wikipedia Orange$
Pour chaque chemin d'un état $s$ à un état $t$ terminal formé de $\varepsilon$ -transitions, ajouter $s - Wikipedia Orange$ à l'ensemble des états terminaux.
Supprimer les $\varepsilon - Wikipedia Orange$ -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 - Wikipedia Orange$ est état final dans la deuxième étape. On obtient l'automate de la figure 7.

Autres exemples d'automates finis

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 - Wikipedia Orange$ , est reconnu: le calcul est
$s_0\xrightarrow1 s_1\xrightarrow0 s_2\xrightarrow0 s_1\xrightarrow1s_0\xrightarrow0 s_0 - Wikipedia Orange$ .
On peut se convaincre qu'un entier $n$ mène, depuis l'état initial, à $s_0$ , $s_1$ ou $s_2 - Wikipedia Orange$ , selon que le reste de sa divison par 3 est 0, 1, ou 2.

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

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\} - Wikipedia Orange$ , 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 - Wikipedia Orange$ change.

Langages rationnels et langages reconnaissables: le théorème de Kleene

Article détaillé : 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

Article détaillé : Expression rationnelle.

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.

Expressions rationnelles

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

Un symbole dénotant le mot vide: $\epsilon$ ou $1 - Wikipedia Orange$ ;
une lettre $a$ de l'alphabet $A - Wikipedia Orange$ ;
une union (ou somme) de deux expressions rationnelles $M$ et $N$ , notée $E= M|N$ ou $E= M+N - Wikipedia Orange$
une concaténation (ou un produit) de deux expressions rationnelles $M$ et $N$ , notée $E= M\cdot N$ ou simplement $E= MN - Wikipedia Orange$
une répétition d'une expression rationnelle $M$ notée $E=M^* - Wikipedia Orange$ .

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) - Wikipedia Orange$ et est défini récursivement, à partir de l'expression.

Construction d'automates finis à partir des expressions rationnelles

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

Automate pour l'union

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)^* - Wikipedia Orange$

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

la méthode de Thompson^[3].
Elle 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 méthode de Glushkov^[4].
Cette méthode, attribuée à l'informaticien Glushkov (en), 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 - Wikipedia Orange$ -transitions de l'automate de Thompson.

la méthode des quotients ou résiduels, attribuée à Brzozowski (en)^[5].
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 $+ - Wikipedia Orange$ .

Aucune de ces méthodes ne donne directement l'automate minimal d'un langage. Une méthode moins systématique consiste simplement à construire des automates pour la réunion, le produit et l'étoile de langages, et d'opérer récursivement :

Soit $\mathcal{A}(M)$ (respectivement $\mathcal{A}(N )$ ) l'automate fini reconnaissant le langage dénoté par l'expression rationnelle $M$ (respectivement $N - Wikipedia Orange$ ). Les constructions sont les suivantes:

Automate $\mathcal{A}(M|N) - Wikipedia Orange$ pour l'union :
Il suffit de faire l'union disjointe des automates $\mathcal{A}(M)$ et $\mathcal{A}(N) - Wikipedia Orange$ .

Automate $\mathcal{A}(M\cdot N) - Wikipedia Orange$ pour le produit :
L'automate a pour états les états de $\mathcal{A}(M)$ et de $\mathcal{A}(N)$ . Les états initiaux sont ceus 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) - Wikipedia Orange$

Automate $\mathcal{A}(M^*) - Wikipedia Orange$ pour l'étoile :
On part de l'automate $\mathcal{A}(M)$ que l'on augmente de deux états $i$ et $t$ . On ajoutes des $\varepsilon - Wikipedia Orange$ -transitions
de $i$ à tout état initial de $\mathcal{A}(M) - Wikipedia Orange$
de tout état final de $\mathcal{A}(M)$ à $t - Wikipedia Orange$
de $i$ à $t$ et de $t$ à $i - Wikipedia Orange$ .
L'état $i$ (resp. $t$ ) est l'état initial (resp. final) de $\mathcal{A}(M^*) - Wikipedia Orange$ .

Autres modèles pour les langages rationnels

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 - Wikipedia Orange$ .)

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 gframmaire, 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 - Wikipedia Orange$ .

Systèmes d'équations linéaires

Fig. 7 : Un automate reconnaissant $a^*b^* - Wikipedia Orange$

A 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. 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 - Wikipedia Orange$ . On a alors :

$L_q =\bigcup_{r \in Q} A_{q,r}\cdot L_r \cup F_q - Wikipedia Orange$

où

$F_q = \begin{cases}\{\varepsilon\} & q \in F \\ \varnothing & q \notin F \end{cases} - Wikipedia Orange$

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} - Wikipedia Orange$ .

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^* - Wikipedia Orange$

En reportant dans la première, on obtient :

$L_1=aL_1\cup b^* - Wikipedia Orange$

et le lemme d'Arden donne :

$L_1=a^*b^* - Wikipedia Orange$

Note : Les ensembles $A_{q,r} - Wikipedia Orange$ 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.

Minimisation d'un automate fini

Article détaillé: Minimisation DFA (en)

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 (voir les livres cités en référence). 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 correspondant, et en testant l'égalité des deux automates obtenus.

Monoïde de transition et monoïde syntaxique

Article détaillé : 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 - Wikipedia Orange$ donnée par

$q\sigma(w)=w\cdot q - Wikipedia Orange$

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

$\sigma(xy)=\sigma(x)\sigma(y) - Wikipedia Orange$

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^*) - Wikipedia Orange$ 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.

Implémentation

Un automate fini peut être représenté en utilisant une table de transition d'état. On l'implémente 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.

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

Notes

↑ Droste et al. 2009
↑ En fait, on peut rencontrer à peu près toutes les situations envisageables. Il a été démontré (G. Jirásková. « Magic numbers and ternary alphabet », dans V. Diekert and D. Nowotka (éditeurs), Developments in Language Theory, Lecture Notes in Comput. Sci. 5583(2009) p. 300–311. Springer-Verlag) que, sur un alphabet à trois lettres, il existe, pour tous $n, N$ avec $n\le N\le 2^n$ , un automate non déterministe à $n$ états, pour lequel l'automate déterministe équivalent a $N - Wikipedia Orange$ états.
↑ Thompson 1968. Elle est attribuée à McNaughton et Yamada dans Hopcroft et al. 2007
↑ Glushkov 1961
↑ Brzozowski 1964

Bibliographie

Olivier Carton, Langages formels, calculabilité et complexité, Vuibert, 2008 (ISBN 978-2-7117-2077-4)

Manfred Droste, Werner Kuich et Heiko Vogler, Handbook of Weighted Automata, Springer-Verlag, 2009 (ISBN 3642014917)

John E. Hopcroft, Rajeev Motwani, et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Prentice Hall, 2007 (ISBN 0321462254).
Troisième édition

Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003 (ISBN 978-2-7117-4807-5).
Traduction anglaise avec corrections: Elements of Automata Theory, Cambridge University Press 2009, (ISBN 9780521844253)

Références historiques

John A. Brzozowski (en), « Derivatives of regular expressions », dans J. Assoc. Comput. Mach., vol. 11, 1964, p. 481–494

Victor M. Glushkov (en), « The abstract theory of automata », dans Russian Math. Surveys, vol. 16, 1961, p. 1–53

Ken Thompson, « Regular expression search algorithm », dans Comm. Assoc. Comput. Mach., vol. 11, 1968, p. 419–422

Voir aussi

Sur les autres projets Wikimedia :

Automate fini, sur Wikimedia Commons
Automate fini, sur le Wiktionnaire

Articles connexes

Lien externe

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°4, p. 409-433.

Portail de l'informatique théorique

[0] Droste et al. 2009

[1] En fait, on peut rencontrer à peu près toutes les situations envisageables. Il a été démontré (G. Jirásková. « Magic numbers and ternary alphabet », dans V. Diekert and D. Nowotka (éditeurs), Developments in Language Theory, Lecture Notes in Comput. Sci. 5583(2009) p. 300–311. Springer-Verlag) que, sur un alphabet à trois lettres, il existe, pour tous $n, N$ avec $n\le N\le 2^n$ , un automate non déterministe à $n$ états, pour lequel l'automate déterministe équivalent a $N - Wikipedia Orange$ états.

[2] Thompson 1968. Elle est attribuée à McNaughton et Yamada dans Hopcroft et al. 2007

[3] Glushkov 1961

[4] Brzozowski 1964

[1]

[2]

[3]

[4]

[5]

encyclopédie par wikipédia

Affichages

Automate fini

Sommaire

Aperçu

Définitions formelles

Automate fini

Automate complet, automate émondé

Automate fini déterministe

Extensions des automates finis

Déterminisation d'un automate fini

Automates asynchrones

Autres exemples d'automates finis

Langages rationnels et langages reconnaissables: le théorème de Kleene

Expressions rationnelles et langages rationnels

Expressions rationnelles

Construction d'automates finis à partir des expressions rationnelles

Autres modèles pour les langages rationnels

Grammaires et les langages rationnels

Systèmes d'équations linéaires

Minimisation d'un automate fini

Monoïde de transition et monoïde syntaxique

Implémentation

Notes

Bibliographie

Références historiques

Voir aussi

Articles connexes

Lien externe

dernières news sur Orange.fr