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.

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

Illustration 1: Automates à états finis

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

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.

Illustration 2: Automate fini déterministe

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 automateUn 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 transition 2

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 .

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

Illustration 3: Automate fini déterministe complet

seulement si δ(q, a) p ∈

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 finalL'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énientsIl 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 transitionReprenons 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,

Illustration 4: Automate fini indéterministe

δ(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.

E xemple 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 transitionssont 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é) ; ilpeut y en avoir plusieurs par case, ou aucun. Les états particuliers sont signalés dans lesderniè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 sefaire directement à partir de n’importe quelle grammaire algébrique.Soit G = (Σ, V, S, P ) une grammaire algébrique. On rappelle les notations : V désignel’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 depile), il nous suffit d’un état : soit E = {s0}.Les symboles de pile sont les symboles terminaux et les variables : Γ = Σ U V . Lesymbole 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îten 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 Pest 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.