Introduction
Un automate est un outil fondamental en Informatique, où il intervient notamment en
compilation des langages informatiques (procédé permettant de passer d'un langage de haut
niveau en langage machine binaire). En effet, les automates interviennent dans le cadre de
deux phases d'analyse: analyse lexicale (automates finis) et analyse syntaxique (automates à
pile).
Qu'est ce qu'un automate? Quels sont les différents types d'automates et comment
fonctionnent-ils? Quels sont leurs liens avec les différents types de grammaire? Voilà autant
de questions auxquelles nous essaieront de répondre lors de cet exposé.
I . Définition d'un automate
De façon très informelle, un automate est un ensemble “d’états du système”, reliés entre eux
par des “transitions” qui sont marquées par des symboles. Étant donné un “mot” fourni en
entrée, l’automate lit les symboles du mot un par un et va d’état en état selon les transitions.
Le mot lu est soit accepté par l’automate, soit rejeté.
II. Automates à états finis
Un automate à états finis , en anglais finite state automaton ou finite state machine (FSA,
FSM), est une machine abstraite utilisée en théorie de la calculabilité et dans l'étude des
langages formels. L'automate est dit «à états finis » car il possède un nombre fini d'états
distincts: il ne dispose donc que d'une mémoire limitée.
Pour représenter de façon très intuitive un automate fini (Q, Σ, δ, q0, F), on peut utiliser un
graphe de transition constitué des éléments suivants :
• Un ensemble de sommets (chaque sommet représente un élément de Q).
• Un ensemble d’arcs entre les sommets valués par un symbole de σ (un arc entre les
états q et q′ valué par le symbole s signifie que δ(q, s) = q′).
• L’état initial q0 est marqué par une flèche entrante.
• Les états finaux F sont entourés d’une double ligne.
Illustration 1: Automates à états finis
Il existe plusieurs types de machines à états finies. Les « accepteurs » produisent en sortie
une réponse « oui » ou « non », c'est-à-dire qu'ils acceptent (oui) ou rejettent (non) l'entrée.
Les systèmes de reconnaissance classent l'entrée par catégorie. Enfin, les capteurs sont
employés pour produire un certain résultat en fonction de l'entrée.
Les automates finis peuvent caractériser des langages (c'est-à-dire, des ensembles de mots)
finis (le cas standard), des langages de mots infinis (automates de Rabin, automates de
Büchi1), ou encore divers types d'arbres (automates d'arbres).
Un langage reconnu par un automate est un langage engendré par une expression régulière.
La correspondance se fait entre:
L’axiome S de la grammaire L' état initial de l’automate
Les variables de la grammaire Les états de l'automate
Les règles de la grammaire Les transitions ou les sorties de
l'automate
Tableau 1: Relation Grammaire régulière-Automate à états finis
Il existe trois types d'automates à états finis: les automates déterministes, les automates
indéterministes (non-déterministes) et les automates complets.
II.1 Automates déterministes
Un automate est déterministe si, pour chacun de ses états, il y a au plus une transition pour
chaque étiquette possible. S'il y en a exactement une, on parle alors d'automate déterministe
complet.
Un automate déterministe A à nombre fini d’états est un quintuplet A= (Q, Σ, δ, q0, F) où
• Q est ensemble fini d’états
• Σ est un vocabulaire
• δ une fonction de transition de Q x Σ dans Q
• q0, l’état initial est un élément de Q
• F, l’ensemble des états finaux, est inclus dans Q
Illustration 2: Automate fini déterministe
1 Un automate de Büchi déterministe opère sur des mots infinis. Un mot infini est accepté si
l'automate de Büchi passe un nombre infini de fois par les états acceptants lorsqu'il lit ce mot.
Fonctionnement de l'automate
Le processus commence à l’état de départ q0. Les symboles(« lettres » pour être plus
simple) du mot sont lus les uns après les autres. À la lecture de chaque symbole, on emploie
la fonction de transition δ pour se déplacer vers le prochain état (en utilisant l’état actuel et
le caractère qui vient d’être lu). Le mot est reconnu si et seulement si le dernier état (i.e.,
l’état correspondant à la lecture du dernier caractère du mot) est un état de F.
Une configuration d’un automate est un couple (q, w) où q est l’état courant et w le mot qui
reste à analyser.
Une transition d’un automate relie deux configurations successives :
(q, aw) →M (p, w) si et seulement si δ(q, a) = p où δ représente la fonction de transition.
Une séquence de transitions relie deux configurations : (q, w) → M (p, v) si et seulement si :
• soit q = p et w = v
• soit (q, w) →M (r, u) et (r, u) →*M (p, v)
Lors de l’arrêt, la machine est dans l’une des trois configurations suivantes :
• Le mot n’est pas entièrement lu mais aucune transition n’est possible : le mot est
rejeté.
• Le mot a été lu, mais l’état dans lequel se trouve la machine n’est pas un état final : le
mot est rejeté.
• Le mot a été lu, et l’état dans lequel se trouve la machine est un état final, marqué
par un double cercle : le mot est accepté (on dit aussi reconnu).
Reconnaissance d'un langage par un automate
Un mot w de longueur n est reconnu ou accepté par un automate fini, s’il existe un chemin
menant de q0 à un état final de F étiqueté par la suite de lettres du mot w.
Le chemin est alors une suite d’arcs étiquetés, pour i de 1 à n.
Le mot w est égal à la concaténation des étiquettes: a1...an.
k0 est l’état initial q0.
kn est un état final.
L’ensemble des mots acceptés par un automate fini A forme le langage reconnu par cet
automate. On le note : L(A) . Autrement dit, A reconnaît tous les mots de L, et A refuse tous
les mots de Σ* (* désigne l'étoile de Kleene) qui ne sont pas dans L.
Le langage L(A) accepté par un automate A est défini par :
L(A) = {w | (q0, w) →*A(f, ε) avec f ∈ F}
Table de transition2
On peut associer à un automate une table de transition qui décrit de manière extensive la
fonction de transition δ :
• Une colonne correspond à un caractère de l’alphabet.
• Une ligne correspond à un état de l’automate (l’état initial est précédé d’une flèche
“→”; l’état final d’une étoile “*”)
La valeur δ(q, a) pour q ∈ Q, a ∈ Σ correspond à l’état indiqué à l’intersection de la ligne q
et de la colonne a. Notons qu’à partir de cette table il est aisé de retrouver l’ensemble des
2 On peut associer une table de transition à n'importe quel type d'automate
états ainsi que l’alphabet et donc d’identifier exactement l’automate.
Considérons la table de transition ci-dessous associée à l'automate de l'illustration 2:.
Il correspond à l’automate (Q, Σ, δ, q0, F) avec
• Q = {1, 2}
• Σ = {a, b}
• δ(1, a) = 1, δ(1, b) = 2, δ(2, a) = 1, δ(2, b) = 2
• q0 = 1
• F = {2}
Il est facile de voir que le langage de cet automate est constitué exactement des mots
composés de a et de b qui se terminent par un b.
✔ Automates déterministes complets
Un automate fini et déterministe est complet si et seulement si d est une fonction totale sur
Q ¥ S. De chaque état, il part alors exactement un arc étiqueté par chacune des lettres de
l’alphabet S.
Quand la fonction est non-totale, l’automate fini peut se trouver bloqué à la lecture d’une
lettre. Un automate fini complet ne sera jamais bloqué, quitte à contenir des états superflus :
les états-poubelles.
Tout automate déterministe peut être transformé en un automate déterministe complet
reconnaissant le même langage.
Si l’automate déterministe n’est pas déjà complet,
• rajouter un nouvel état (« état poubelle »)
• rajouter les transitions d’étiquettes manquantes en les dirigeant toutes vers cet état
poubelle P ; ne pas oublier les transitions de P lui-même vers P .
Illustration 3: Automate fini déterministe complet
II.2 Automates finis indéterministes (non-déterministes)
Un automate fini non-déterministe est un automate tel que dans un état donné,il peut y
avoir un nombre quelconque de transitions à partir d'un état donné pour une étiquette
donnée.
Un automate à états finis indéterministe est défini de la même façon qu'un automate fini
déterministe, c’est la fonction de transition δ qui diffère ici de celle utilisée par les
automates finis déterministes. (une fonction de transition: δ qui associe à tout état q ∈ Q et
tout symbole s ∈ Σ un sous ensemble de Q noté δ(q, s).)
Une transition d’un automate indéterministe relie deux configurations : (q, aw) * (p, w) si et
seulement si δ(q, a) ∈ p
Illustration 4: Automate fini indéterministe
Dans le cas d'un automate fini indéterministe, une cellule de la table de transition contient
un sous-ensemble d’états (éventuellement vide).
Fonctionnement d'un automate fini indéterministe.
Le fonctionnement d’un tel automate n’est donc pas totalement « déterminé », car on ne sait
pas quel état l’automate va choisir. Un tel automate accepte un mot si, parmi tous les choix
possibles, il y a une séquence de transitions qui aboutit à un état final
L'automate A démarre dans l'état de départ, ou dans chacun des états de départ s'il y en a
plusieurs. Concrètement, lorsqu'il doit prendre plusieurs états à la fois, on peut
raisonnablement considérer qu'il se duplique. Le ou les automate(s) reçoi(ven)t en entrée la
même séquence w de symboles. Il(s) emploie(nt) la fonction de transition T pour déterminer
le (les) prochains état(s) atteignable(s). En effet, pour chaque exemplaire de l'automate, la
fonction détermine le(s) futur(s) état(s) en prenant en compte non seulement le symbole
venant d'être lu, mais aussi l'état actuel. On dit que l'automate non déterministe A accepte
l'entrée w si au moins un état terminal est atteint au terme de la lecture de la séquence
d'entrée. Sinon, A rejette w.
Avantages et inconvénients
Il n’est pas commode d’implanter pratiquement un automate indéterministe. Leur intérêt
majeur réside dans le fait qu’ils sont faciles à concevoir, permettent de modéliser facilement
des problèmes complexes et qu’on dispose d’un algorithme pour les déterminiser. Ils
peuvent être convertis en des automates finis déterministes.
Table de transition
Reprenons l'automate de l'illustration 4 qui reconnaît les mots définis sur l’alphabet {a, b, c}
qui commencent par a et qui finissent par c.
La table associée à cet automate est alors :
Comme pour les automates déterministes, nous nous
introduisons la fonction de transition étendue aux mots, δ.
Elle se définit récursivement comme suit.
• A partir d’un état q en lisant le mot vide є (le mot vide ne contient aucun symbole et
est toujours noté є), on reste dans l’état q, i.e., ∀ q ∈ Q, δ(q, є) = {q}
• Étant donné un mot c se terminant par a ∈ Σ (i.e., c = c′a avec c′ ∈ Σ ∪ {є}), et un
état q de Q,
δ(q,c) = δ(q, c′a) = ∪ δ(p,a), p ∈ δ(q, c′)
On peut maintenant définir le langage L(A) accepté par un automate fini déterministe A =
(Q, Σ, δ, q0, F). L(A)={c | δ(q0,c) ∩ F ≠ ∅}
Déterminisation d'un automate fini indéterministe
Un automate fini déterministe est aussi non-déterministe. Donc tout langage reconnu par un
automate fini déterministe est reconnu par un automate fini non-déterministe. Plus
surprenant, la réciproque est aussi vraie (Théorème de Rabin-Scott).
Considérons un automate fini non-déterministe An = (Qn, Σ, δn, q0, Fn) et construisons un
automate fini déterministe Ad = (Qd, Σ, δd, {q0}, Fd) qui reconnaît exactement le même
langage.
• Les alphabets de An et de Ad sont identiques.
• Les états de départ sont respectivement q0 et le singleton {q0}.
• Qd est constitué de tous les sous-ensembles de Qn.
• Fd est l’ensemble des sous-ensembles de Qn qui contiennent au moins un élément de
Fn.
• Étant donné un sous ensemble S de Qn et un symbole a ∈ Σ, on définit la fonction de
transition δd(S,a) de la manière suivante: δd(S,a) = ∪ δn(q, a). avec q ∊ S
Dans le pire des cas, l'automate déterministe produit est exponentiellement plus grand (en
nombre d'états) que l'automate non déterministe, mais il est en général possible d'en
diminuer considérablement le nombre d'états.
Exemple
Ceci est un automate fini non-déterministe reconnaissant les mots de l’alphabet {a,b} qui
terminent par bab.
Essayons maintenant de le déterminiser en construisant un nouvel état à partir de chaque
sous ensemble d’état possible.
Remarquons que les états {1}, {2}, {3}, {0,2}, {0,3}, {1,2}, {2,3}, {0,1,2}, {1,2,3}, {0,2,3}
sont impossible à atteindre et peuvent être “retirés” de l’automate.
En pratique, lors de la conversion, on ne crée pas immédiatement tous les états de
l’automate fini déterministe. Les états “utiles” sont crées quand on en a besoin en suivant la
méthode de construction ci-dessous :
• Qd est initialisé à ∅ et soit E un ensemble d’états initialisé à E = {{q0}}
• Tant que E est non vide,
• choisir un élément S de E (S est donc un sous ensemble de Qn),
• ajouter S à Qd,
• pour tout symbole a ∈ Σ,
• calculer l’état S′ = ∪q ∈ S δn(q, a)
• si S′ n’est pas déjà dans Qd, l’ajouter à E
• ajouter un arc sur l’automate entre S et S′ et la valuer par a
II.3 Applications
Les automates à états finis sont utilisés dans divers domaines tels que:
➔ Analyse lexicale
Les éléments lexicaux d’un langage de programmation (mots clés, symboles de
ponctuation, identificateurs, constantes) forment un langage d’ordinaire rationnel. Il est
commode de décrire ces éléments lexicaux en donnant des expressions rationnelles et de
structurer cette description en catégories lexicales.
Il est alors possible de calculer automatiquement un analyseur lexical. On pro-
cède de la manière suivante :
• Calcul d’un automate non-déterministe équivalent à l’expression rationnelle.
• Déterminisation et minimisation.
• Production des tables de transition de l’automate, auxquelles on associe des actions
simples : stockage de l’élément lexical, production de sa catégorie.
➔ Édition de texte et recherche de motifs
De nombreux algorithmes utilisés par les outils de traitement de texte calculent ou utilisent
des automates à états finis.
➔ Saisie de données
De nombreuses applications comportent des phases de saisies de données
dont le langage est rationnel. L’utilisation de la programmation par automate
présente quatre avantages principaux :
• On obtient une spécification précise du format des données.
• On n’est pas tenté d’apporter des restrictions arbitraires « justifiées » par l’idée
souvent fausse d’obtenir un code plus simple.
• On réduit l’effort de programmation à l’essentiel, tout en réduisant le risque d’erreur.
Le logiciel obtenu est plus évolutif.
➔ Applications parallèles ou réactives
Citons, pour terminer, le fait que la notion d’automate à nombre fini d’états est
un des modèles particulièrement utiles pour concevoir, modéliser, tester... des
applications réactives (temps réel entre autres) ou parallèles (protocoles...).
III. Automates à pile
Un automate à pile est semblable à un automate fini mais il dispose également d'une pile.
Ainsi, Un automate à pile (non déterministe) est un 7-uplet ,
où
• est l'ensemble d'états,
• est l'alphabet d'entrée,
• est l'alphabet de pile,
• est la fonction de transition (la notation
désignant l'ensemble des parties),
• est le symbole de fond de pile,
• est l'état initial,
• est l'ensemble des états terminaux.
Une configuration de l'automate est un triplet . Un calcul de
l'automate sur un mot est une série de transitions à partir de la configuration
(q0,w,γ0). À partir d'une configuration (q,σw,γβ), où σ et γ sont des lettres de Σ et Γ, les
transitions possibles sont :
• lorsque ,
• lorsque .
On dit qu'un mot est accepté par l'automate s'il existe une série de transitions qui conduit à
une configuration acceptante, notion qui peut être définie de deux façons :
• Reconnaissance par pile vide.
Ce mode de reconnaissance autorise un automate à pile à accepter une chaîne si, à
partir de l’état initial, elle peut être entièrement lue en vidant la pile. Il n’y a donc pas
lieu de préciser un sous-ensemble d’états acceptants, il est sous-entendu que F = E
(tous les états sont acceptants).
• Reconnaissance par état acceptant.
Avec cette convention, une chaîne testée par un automate à pile A est acceptée si, à
partir de l’état initial, elle peut être entièrement lue en arrivant à un état de F , ceci
quel que soit le contenu de la pile à ce moment-là. La pile est supposée vide au départ
ou peut contenir le symbole de fond de pile.
Dans le cas non déterministe, cette distinction n'a pas d'importance car les deux types
d'automates sont équivalents.
Le langage L(A) reconnu par l'automate à pile A est l'ensemble des mots de Σ * qui
permettent de passer de l'état initial à l'état final en démarrant avec une pile contenant le
symbole de fond de pile et en terminant avec une pile vide. Deux automates à pile
reconnaissant le même langage seront dits équivalents. Chaque langage défini par une
grammaire algébrique est reconnu par un automate à pile et réciproquement.
La plupart des langages de programmation sont décrits par une grammaire algébrique.
L'analyse syntaxique d'un programme, qui est une des premières opérations effectuée par un
compilateur, peut donc être effectuée par un automate à pile. Il existe des outils
automatiques pour construire l'automate à pile à partir d'une description de la grammaire du
langage (par exemple Lex et Yacc en C).
Un automate à pile peut être représenté comme un automate, à l'aide d'un graphe orienté et
étiqueté, à condition de préciser l’action sur la pile de chacune des transitions. En fait, les
symboles de pile servent d’aiguillages plutôt que de compteurs : une transition est
verrouillée si le symbole à dépiler ne correspond pas au haut de pile courant.
Pour une représentation graphique complète d’un automate à pile, il faut préciser l’action
sur la pile avec l’étiquette de chaque flèche. Les conventions diffèrent selon les auteurs. On
peut adopter la suivante, qui a l’avantage de séparer distinctement le symbole lu dans la
chaîne testée et les symboles de pile (formellement, ce sont parfois les mêmes...) :
Un automate à pile peut se décrire aussi à l’aide d’une table dans laquelle les transitions
sont spécifiées. Les lignes correspondent aux états, les colonnes aux étiquettes possibles.
Dans les cases figurent les triplets (état d’arrivée ; symbole dépilé ; symbole empilé) ; il
peut y en avoir plusieurs par case, ou aucun. Les états particuliers sont signalés dans les
dernières colonnes.
II.1 Construction d'un automate à pile à partir d'une grammaire algébrique
La construction très générale qui suit paraît un peu formelle ; néanmoins, elle peut se
faire directement à partir de n’importe quelle grammaire algébrique.
Soit G = (Σ, V, S, P ) une grammaire algébrique. On rappelle les notations : V désigne
l’ensemble des variables, l’axiome S ∈ V , et P est l’ensemble des règles de production,
qui sont de la forme A → M où A ∈ V et M ∈ (Σ U V)*.
Pour obtenir un automate reconnaissant par pile vide (donc avec un symbole initial de
pile), il nous suffit d’un état : soit E = {s0}.
Les symboles de pile sont les symboles terminaux et les variables : Γ = Σ U V . Le
symbole initial de pile est S .
Chaque règle de grammaire A → M , où M ∈ (Σ U V)* , fournit une transition
d’étiquette vide, dont l’effet sur la pile est de remplacer A par la chaîne M :
ε
[s0 , A] → [s0 , M ]
Il reste encore à ajouter les transitions qui dépilent un symbole terminal quand il apparaît
en haut de la pile. Ce symbole passe alors en étiquette. Pour tout a ∈ Σ :
a
[s0 , a] → [s0 , ε]
L’automate à pile obtenu est de la forme A = ( Σ , {s0}, so , Σ U V, S , δ ) .
II.2 Grammaire algébrique associée à un automate à pile
Étant donné un langage reconnu par un automate à pile (à transitions généralisées), notre
objectif est maintenant de construire une grammaire algébrique produisant ce langage.
Les variables de la grammaire.
Les variables de la grammaire sont les triplets (i, P, k) où i et k sont des états, et P
est un symbole de pile. La variable S = (so , ∆ , f) joue le rôle d’axiome.
Les règles de grammaire.
II.3
Automate à pile non déterministe
On dit qu'un mot est accepté par l'automate s'il existe une série de transitions qui conduit à
une configuration acceptante, notion qui peut être définie de deux façons :
• Pour les automates à reconnaissance par pile vide, les configurations acceptantes sont
les configurations de la forme (q,ε,ε) où est un état quelconque. Autrement
dit, il est possible d'arriver à vider entièrement la pile au moment où on termine la
lecture du mot.
• Pour les automates à reconnaissance par état final, les configurations acceptantes sont
les configurations de la forme (q,ε,β) où est un état final.
Dans le cas non déterministe, cette distinction n'a pas d'importance car les deux types
d'automates sont équivalents.
Le langage reconnu par l'automate est l'ensemble des mots de Σ * qui sont
acceptés.
Automate à pile déterministe
Un automate à pile déterministe est défini de la même manière qu'un automate à pile non
déterministe, à l'exception de la fonction de transition. Dans le cas déterministe, δ est une
fonction partielle . De plus, lorsque δ(q,ε,γ) est définie,
alors δ(q,σ,γ) ne peut être définie pour aucun . Ainsi, au plus une transition est
possible à partir de n'importe quelle configuration.
On distingue de même deux types de reconnaissance, par état final ou par pile vide. Les
automates déterministes avec reconnaissance par état final sont plus puissants que les
automates avec reconnaissance par pile vide. Plus précisément, un langage L peut être
reconnu par le second type d'automate s'il peut être reconnu par un automate du premier
type et qu'aucun mot du L n'est préfixe d'un autre. Par exemple, le langage anbn(n > 0) est
reconnu par les deux types d'automates déterministes, mais le langage an ne l'est que par
automate déterministe par état final.