Automate fini

Un automate fini (en anglais finite state machine ou finite automaton) est un modèle de calcul d’un ordinateur primitif, composé de plusieurs états et de plusieurs transitions, et qui peut accepter ou rejeter un mot qu’on lui donne.

Exemple

Décrivons d’abord l’automate fini de manière informelle, à l’aide d’un diagramme d’états :

Exemple d’un automate fini simple

L’automate est constitué d’états ; sur la figure, ce sont les trois états ronds q₀, q₁ et q₂. Entre ces états, il y a des transitions, ce sont les flèches. L’automate doit aussi avoir un état initial, ici l’état q₀. L’état initial est souvent représenté par une flèche qui y arrive sans partir d’aucun état. De plus, l’automate a en général un état final, que nous représentons par un double trait ; sur la figure, c’est l’état q₂.

Un automate ainsi construit accepte certains mots. Nous donnons des mots à l’automate et il essaie de les accepter. S’il les accepte, il répond OUI, sinon il répond NON. Notre automate essaie d’accepter des mots composés des lettres « a, b, c », nous pouvons donc essayer d’accepter le mot « abbc ».

Nous commençons dans l’état initial q₀ et le mot d’entrée est « abbc ». Ensuite, nous suivons les flèches.

Nous lisons le mot de la manière habituelle, de gauche à droite, c’est-à-dire que nous prenons d’abord le symbole « a ». La flèche pour l’entrée « a » mène à l’état q₁ ; nous y passons et nous retirons le symbole « a » du mot. Il reste en entrée le mot « bbc » :

La flèche pour l’entrée « b » revient vers le nœud q₁. Nous retirons de nouveau la première lettre et il reste en entrée le mot « bc ». Nous restons encore dans l’état q₁. Enfin, il reste en entrée le mot « c ». Depuis l’état q₁, la flèche pour l’entrée « c » nous envoie dans l’état q₂.

Nous avons épuisé toutes les lettres du mot d’entrée et nous sommes dans l’état q₂, qui est un état final. Cet automate fini accepte donc le mot « abbc ».

Si nous n’étions pas à la fin dans un état d’acceptation, l’automate n’accepterait pas le mot. De même, l’automate n’accepterait pas le mot si, dans un état, nous n’avions nulle part où aller. Par exemple, pour l’entrée « ab », nous arriverions dans l’état q₁ et nous y resterions bloqués : l’automate n’accepte pas un tel mot. Si nous testons le mot « aabbc », nous n’avons pas de chance non plus, car de l’état q₁ il ne part aucune flèche pour la lettre « a ».

L’automate fini sert donc à reconnaître un certain ensemble de mots. En pratique, nous pourrions utiliser un automate, par exemple, pour déterminer si un mot d’entrée donné est une adresse e-mail valide.

Définition de l’automate fini

Nous devons formaliser l’idée intuitive précédente de ce qu’est un automate fini pour pouvoir ensuite travailler plus facilement avec les automates.

Nous disons qu’un automate fini (déterministe) est un quintuplet (Q ; Σ ; δ ; q₀ ; F), où

Q est un ensemble fini d’états,
Σ (sigma majuscule) est l’alphabet (un ensemble fini de symboles ou de lettres),
δ: Q × Σ ⟶ Q est la fonction de transition,
q₀ ∈ Q est l’état initial,
F ⊆ Q est l’ensemble des états finals (d’acceptation).

Revenons à l’automate précédent,

nous pouvons dire que l’ensemble d’états Q contient trois états Q = {q₀ ; q₁ ; q₂}. L’alphabet Σ contient les lettres avec lesquelles nous pouvons former les mots que l’automate acceptera ou rejettera. Ici, ce sera probablement l’alphabet Σ= {a ; b ; c}, mais ce peut être aussi n’importe quel sur-ensemble de celui-ci. L’état initial q₀ est l’état q₀, rien ne change là. L’ensemble des états finals ne contient dans cet automate qu’un seul état, F = {q₂}.

Par fonction de transition, nous entendons ces trois flèches munies de lettres. Si la notation δ: Q × Σ ⟶ Q te trouble, elle signifie simplement que δ est une fonction (ou plutôt une application) qui prend deux paramètres : un état de Q et une lettre de Σ. Une fois appelée, la fonction renvoie un nouvel état. Nous pourrions définir notre fonction de transition par un tableau ainsi :

$\begin{array}{ccc} Q & Σ & \to Q \\ q_{0} & a & q_{1} \\ q_{1} & b & q_{1} \\ q_{1} & c & q_{2} \end{array}$

Si nous appelons donc δ(q₁, c), nous appliquons la troisième ligne et la fonction répond par l’état q₂, tout comme le diagramme. Si nous sommes dans l’état q₁ et que la lettre « c » est en entrée, nous arrivons dans l’état q₂. Avant de définir formellement ce que signifie qu’un automate accepte un mot, nous allons nous appuyer sur la compréhension intuitive de cette notion et voir d’autres exemples.

Autres exemples

Construis un automate qui travaille sur l’alphabet binaire, c’est-à-dire Σ= {0 ; 1}, et qui accepte uniquement les mots qui se terminent par un 1. Par exemple, il accepte les mots 1, 01, 000001, 0101011.

Notre automate a deux états : l’état initial q₀ et l’état final q₁. Dès que le chiffre 1 est en entrée, nous passons dans l’état final q₁ et nous y restons. En revanche, si le chiffre 0 est en entrée, nous passons dans l’état non final q₀ et nous y restons aussi.
Construis un automate sur l’alphabet binaire qui accepte uniquement les mots dont la première lettre est différente de la dernière.

Dès la première étape, l’automate se divise en deux « sous-automates ». Si le mot commence par un zéro, l’automate entre dans la partie gauche et y reste ; s’il commence par un un, il passe dans la partie droite. Ensuite, c’est classique : si nous sommes dans la partie gauche et que 1 est en entrée, nous passons dans l’état final et nous y restons. Si 0 est en entrée, nous passons dans l’état q₁, qui n’est pas final.

Contrairement aux automates précédents, cet automate a plusieurs états finals, c’est-à-dire F = {q₃ ; q₄}.
Construis un automate sur l’alphabet binaire qui accepte uniquement les mots qui ne contiennent pas deux zéros consécutifs.

Cet automate est intéressant pour deux raisons. La première est qu’il accepte le mot vide. Nous pouvons essayer de donner le mot vide à l’automate, et celui-ci l’accepte si l’état initial est en même temps un état final, ce qui est le cas ici. Comme le mot vide ne contient pas deux zéros consécutifs, c’est bien le résultat attendu. L’autre particularité est que tous les états de cet automate sont finals. Le seul cas où l’automate n’accepterait pas un mot est celui où aucune transition ne part de l’état. Cela arrive dans l’état q₁, qui n’a pas de transition pour 0, car le mot contiendrait alors deux zéros consécutifs.
Construis un automate sur l’alphabet {-,+,.,0,1,…,9} qui accepte uniquement les mots qui représentent un nombre. C’est-à-dire soit un entier comme 2, 548, 98263, soit un nombre décimal comme 5584.48, 3.14 (ici avec un point, comme en programmation), et les deux aussi en version négative avec le signe moins -2, -548, -3.14, et même avec un plus écrit explicitement, c’est-à-dire +2, +548, +3.14. Nous devons en même temps pouvoir écrire le nombre 0.123 simplement sous la forme .123 (sans le zéro du début), avec les deux signes. Nous introduisons une notation auxiliaire : au lieu d’écrire dix transitions pour les dix chiffres, nous utiliserons le symbole N.
Construis un automate sur l’alphabet binaire qui accepte uniquement les mots de la forme 0ⁿ1ⁿ, ce qui signifie que les mots commencent par un certain nombre de zéros, suivis du même nombre de uns. Exemples de tels mots : 0011, 00001111, 01.

Un tel automate ne peut pas être construit, parce que nous ne sommes capables de « mémoriser » nulle part le nombre de zéros. Il faudrait créer plusieurs « sous-automates », comme dans le deuxième exemple, mais il en faudrait une infinité, un pour chaque valeur de n.

Formalisation du calcul de l’automate

Nous avons déjà défini formellement l’automate fini lui-même. Il nous reste à définir ce que fait réellement un tel automate, c’est-à-dire à définir le calcul de l’automate.

Configuration de l’automate : nous disons qu’un couple (q ; w) ∈ Q × Σ^∗ est une configuration de l’automate, où q est l’état actuel dans lequel se trouve l’automate et w est la partie du mot qui n’a pas encore été lue. Σ^∗ désigne l’ensemble de tous les mots que l’on peut former avec les lettres de l’alphabet Σ (l’étoile de Kleene). Le mot vide, que nous notons ε, en fait partie.

Si nous avons un automate (Q ; Σ ; δ ; q₀ ; F) et que nous essayons d’accepter un mot w, l’automate se trouve dans la configuration initiale (q₀ ; w). Si nous revenons à l’automate

et que nous voulons accepter le mot w = abbc, la configuration initiale sera (q₀ ; abbc).

Nous définissons une étape de calcul comme une relation ↦ entre les ensembles (Q × Σ^∗) × (Q × Σ^∗), c’est-à-dire entre des configurations de l’automate. Soit w = w₀w₁… w_n la partie non encore lue du mot w. Nous disons alors que les couples (q₁ ; w₀w₁… w_n) et (q₂ ; w₁… w_n) sont en relation par ↦, ce que nous écrivons

$(q_{1}; w_{0} w_{1} \dots w_{n}) \mapsto (q_{2}; w_{1} \dots w_{n}),$

si et seulement si δ(q₁, w₀) = q₂. Pour revenir à notre exemple, la configuration initiale est (q₀ ; abbc). D’après le diagramme, pour l’entrée « a », nous pouvons passer dans l’état q₁. Nous pouvons donc écrire

$(q_{0}; a b b c) \mapsto (q_{1}; b b c),$

car δ(q₀, a) = q₁. Nous avons ainsi effectué une étape de calcul : nous avons regardé dans quel état nous devions aller pour l’entrée donnée (= la première lettre de la partie non lue du mot), nous y sommes passés et nous avons retiré la première lettre de la partie non lue du mot. Nous avons ainsi obtenu une nouvelle configuration.

La fermeture réflexive et transitive de la relation « étape de calcul » se note ↦ ^∗. Si nous écrivons K₁ ↦ ^∗ K₂, où K₁, K₂ sont des configurations de l’automate, cela signifie que de la configuration K₁ nous pouvons atteindre la configuration K₂ en plusieurs étapes de calcul, c’est-à-dire qu’il existe une suite finie de configurations telle que :

$K_{1} \mapsto K_{11} \mapsto K_{12} \mapsto K_{13} \mapsto \dots \mapsto K_{2}$

Par exemple, dans notre automate, on a (q₀ ; abbc) ↦ ^∗ (q₁ ; bc), car lorsque nous effectuons deux étapes de calcul, il reste le mot « bc » et nous restons dans l’état q₁. Autrement dit, il existe cette suite de configurations :

$(q_{0}; a b b c) \mapsto (q_{1}; b b c) \mapsto (q_{1}; b c)$

L’automate accepte le mot w si et seulement s’il existe q_f ∈ F tel que $(q_{0}; w) \mapsto^{*} (q_{f}; ε)$ Cela signifie que l’automate accepte le mot w si et seulement s’il existe une suite d’étapes de calcul telle qu’à la fin de cette suite nous avons lu le mot entier et nous nous trouvons dans un état final de l’automate. Le fait que nous ayons lu le mot entier est exprimé par le mot vide ε à la place du mot dans la configuration. Notre automate accepte le mot abbc, car il existe cette suite de configurations :

$(q_{0}; a b b c) \mapsto (q_{1}; b b c) \mapsto (q_{1}; b c) \mapsto (q_{1}; c) \mapsto (q_{2}; ε)$

et l’état q₂ est un état final, q₂ ∈ F.

Le langage accepté par l’automate est l’ensemble de tous les mots que l’automate accepte. Le langage d’un automate A se note L(A). On a donc L(A) ⊆ Σ^∗ et

$L (A) = {w \in Σ^{*} | A accepte le mot w}$

Un langage régulier est un langage accepté par un automate fini.

Deux automates finis sont équivalents s’ils acceptent le même langage. Autrement dit, les automates A₁ et A₂ sont équivalents si L(A₁) = L(A₂).

Sources

Chapitres: Automate fini, Automate complet, Automate fini non déterministe, Simulation d’un AFN, Déterminisation d’un AFN

« Précédent: Langages formels

Suivant: Automate complet »