Automates

Ce document présente une introduction complète aux automates finis, destinée aux étudiants et chercheurs en informatique, mathématiques et linguistique. Il couvre les notions fondamentales, les types d'automates, leurs propriétés, ainsi que leurs applications pratiques dans divers domaines.

Un bref historique

La théorie des automates est née de la convergence de plusieurs courants scientifiques : la formalisation du calcul par Church, Gödel et Turing, l'étude des systèmes dynamiques discrets, la théorie de l'information de Shannon, la linguistique formelle de Chomsky, et la conception des circuits électroniques. Le terme « théorie des automates » a été introduit en 1948 par Von Neumann, en référence à un article de McCulloch et Pitts sur les réseaux neuronaux.

Kleene a démontré en 1956 un théorème fondamental affirmant que les langages reconnus par un automate sont exactement les langages rationnels (ou réguliers), décrits par des opérations d'union, produit et étoile. Cette découverte implique que l'ensemble des langages rationnels est fermé par intersection et complément.

Les automates avec sortie, notamment les automates séquentiels, ont été introduits à la fin des années 1950. Ils produisent un mot en sortie au fur et à mesure de la lecture du mot d'entrée, et sont proches des circuits électroniques.

Mots et langages

Un alphabet est un ensemble fini de lettres, par exemple {a, b} ou {A, C, G, T}. Un mot sur un alphabet A est une suite finie de lettres de A, notée par juxtaposition. La longueur d'un mot u, notée |u|, est le nombre de lettres qu'il contient. Le mot vide est noté ε.

Le produit (concaténation) de deux mots u et v est le mot obtenu en mettant u et v bout à bout. Par exemple, le produit de "abra" et "cadabra" est "abracadabra". On note aussi (ab)^3 = "ababab".

Un langage est un ensemble de mots sur un alphabet donné, par exemple {aba, babaa, bb} ou {a^n b^n | n > 0}.

Automates déterministes

Un automate déterministe est un graphe étiqueté avec :

• Un ensemble fini d'états, dont un état initial.
• Un ensemble d'états finaux.
• Des transitions étiquetées par des lettres, avec au plus une transition par lettre depuis chaque état.

Pour savoir si un mot est accepté, on lit ses lettres de gauche à droite en suivant les transitions depuis l'état initial. Si on atteint un état final à la fin de la lecture, le mot est accepté.

Exemple : Considérons l'automate de la figure 1.1 avec états 1 (initial), 2, 3 (finaux) et transitions :

• 1 --a--> 2
• 2 --a--> 2
• 2 --b--> 3
• 3 --a--> 1

Le mot "aab" est accepté car le chemin est 1 --a--> 2 --a--> 2 --b--> 3 (état final).

Le mot "aba" est rejeté car on termine dans l'état 1 non final.

Le mot "abb" est rejeté car il n'y a pas de transition "b" depuis l'état 3.

Langages reconnaissables

Un langage est reconnaissable s'il existe un automate déterministe qui le reconnaît. Par exemple :

• L'automate de la figure 1.2 reconnaît les mots sur {a, b} commençant par "aba".
• L'automate de la figure 1.3 reconnaît les mots binaires représentant des multiples de 3.

Le langage {0^n 1^n | n > 0} n'est pas reconnaissable, car un automate fini ne peut simuler une pile de hauteur non bornée.

Automates non déterministes

Un automate non déterministe peut avoir plusieurs états initiaux et plusieurs transitions avec la même étiquette depuis un même état. Un mot est accepté s'il existe au moins un chemin réussi (du départ à un état final) portant ce mot.

Exemple : L'automate de la figure 1.5 accepte les mots sur {0, 1} contenant la chaîne "010".

Tout automate non déterministe est équivalent à un automate déterministe, mais la déterminisation peut entraîner une explosion exponentielle du nombre d'états.

Automate minimal

À partir d'un automate déterministe, on peut :

• Éliminer les états inaccessibles ou inutiles.
• Minimiser l'automate en identifiant deux états p et q lorsque les mêmes mots permettent d'atteindre un état final depuis p et q.

L'automate minimal est unique à isomorphisme près et possède le plus petit nombre d'états parmi tous les automates déterministes reconnaissant le même langage.

Expressions rationnelles

Les expressions rationnelles (ou régulières) décrivent les langages rationnels à l'aide des opérations :

• Union (+) : L + L′ = {u ∈ A* | u ∈ L ou u ∈ L′}
• Produit (concaténation) : LL′ = {uu′ | u ∈ L et u′ ∈ L′}
• Étoile (*) : L* = union de toutes les puissances L^n, n ≥ 0

Exemple : Pour L = ab + abc et L′ = ab + cab, on a :

• L + L′ = ab + abc + cab
• LL′ = abab + abcab + abccab

Quelques langages rationnels sur A = {a, b} :

• L'alphabet A : a + b
• Ensemble de tous les mots : (a + b)*
• Langage des mots contenant la lettre a : A* a A*
• Langage des mots de longueur impaire : (A^2)* A
• Langage (ab)* formé des mots ε, ab, abab, ababab, ...

Le théorème de Kleene

Le théorème de Kleene affirme qu'un langage est rationnel si et seulement s'il est reconnaissable par un automate. La démonstration fournit un algorithme pour passer d'un automate à une expression rationnelle et inversement.

Exemple : Le langage reconnu par l'automate de la figure 1.1 est donné par l'expression rationnelle :

(aa*ba)* aa* (b + ε)

Le théorème implique aussi que l'intersection et la différence de langages rationnels sont encore rationnels.

Pour illustrer, on cherche une expression rationnelle pour le langage L des mots ne contenant pas la chaîne "010". En partant de l'automate non déterministe reconnaissant les mots contenant "010" (figure 1.5), on détermine un automate déterministe équivalent (figure 1.7), puis on échange les états finaux et non finaux et supprime les états inutiles (figure 1.8). La conversion finale donne par exemple :

(1 + 00*11)* (ε + 00* + 00*1)

Automates séquentiels

Les automates séquentiels sont des automates déterministes produisant un mot de sortie. Ils réalisent des transformations telles que l'addition, la multiplication par une constante, le codage/décodage, ou des opérations sur du texte.

Dans un automate séquentiel, les états initiaux et finaux sont étiquetés par des mots, et les transitions par des couples lettre|mot. La lettre à gauche est l'entrée lue, le mot à droite est la sortie produite.

Exemple : L'automate de la figure 1.9 lit le mot d'entrée 1001101 et produit la sortie 01001100 en suivant les transitions et en concaténant les mots de sortie.

On peut minimiser un automate séquentiel, bien que ce soit plus délicat que pour les automates déterministes. Une fonction est dite séquentielle si elle peut être réalisée par un automate séquentiel. La composition de fonctions séquentielles est séquentielle.

Un automate séquentiel est lettre à lettre si les mots de sortie des transitions sont des lettres. Un automate de Mealy est un automate lettre à lettre avec états initiaux et finaux étiquetés par le mot vide. Un automate de Moore produit ses sorties associées aux états traversés, et peut être simulé par un automate de Mealy et inversement.

Exemple : La figure 1.10 montre un automate séquentiel lettre à lettre réalisant la multiplication par 3 d'entiers représentés en binaire inversé (bits lus de droite à gauche). Par exemple, l'entrée 1011 (représentant 13) produit la sortie 111001 (représentant 39 = 13 × 3).

L'addition d'entiers est aussi séquentielle. En représentant n et m en binaire inversé et en alignant leurs bits, on forme un mot sur l'alphabet {(0,0), (0,1), (1,0), (1,1)}. L'automate de la figure 1.11 réalise cette addition, avec deux états correspondant à la retenue.

Un automate de Mealy peut aussi réaliser la division d'un polynôme à coefficients dans Z/2Z par X² + X + 1, comme illustré en figure 1.12. Le quotient est donné par la sortie, le reste par l'état final.

Les automates séquentiels permettent la multiplication et division par une constante, mais pas la multiplication ou division de deux entiers généraux, qui sont plus complexes.

Exemple : Un filtre à rebonds (figure 1.13) lit une suite de bits commençant et finissant par 0, et modifie certains bits selon leur voisinage. Ce type de filtre est utilisé en traitement d'images pour corriger des imperfections.

Utilisation pratique des automates

Analyse lexicale

Les automates finis sont utilisés en compilation pour construire des analyseurs lexicaux, qui reconnaissent les mots-clés d'un langage. Par exemple, l'automate de la figure 1.14 reconnaît plusieurs mots-clés du langage Java : do, double, final, finally, this, throw, throws.

Modélisation de systèmes finis

Les automates modélisent des systèmes à nombre fini de configurations. Par exemple, un monte-charge avec trois étages et deux boutons (monter, descendre) est modélisé par un automate (figure 1.15).

Un autre exemple classique est le problème du passeur, du loup, de la chèvre et de la salade. L'automate de la figure 1.16 modélise les états possibles sur les rives, avec des transitions correspondant aux traversées autorisées. Il permet de trouver les solutions les plus courtes au problème.

Modélisation de systèmes infinis

Les automates peuvent aussi modéliser des systèmes de taille infinie, notamment pour l'analyse et la vérification de protocoles. Par exemple, un réseau de processus alignés transmettant un témoin est modélisé par un automate séquentiel (figure 1.18), représentant la fonction τ : {T, N}* → {T, N}*.

Un autre automate séquentiel (figure 1.19) calcule la fonction f définie par :

f(n) = n/2 si n est pair
f(n) = 3n + 1 sinon

Cette fonction est liée à la célèbre conjecture de Collatz, non résolue à ce jour.

Industries de la langue

Les automates sont largement utilisés en informatique linguistique, traitement automatique des langues, correction orthographique, génération automatique de texte, et réalisation de dictionnaires électroniques.

L'automate non déterministe de la figure 1.20, dû à Maurice Gross, modélise l'ordre des particules préverbales en français (sans élisions). Par exemple, les phrases "je ne le lui ai pas donné" ou "il n'y en a jamais !" sont correctes, mais "il se le lui est fait volé ne l'est pas."

Les dictionnaires électroniques peuvent être représentés par des arbres ou des automates. La représentation par automate est beaucoup plus compacte et efficace pour la recherche et la mise à jour.

Exemple : L'arbre de la figure 1.21 représente les mots {bal, bals, ban, bans, do, don, dons, doux, pal, pals, pan, pans}, tandis que l'automate minimal de la figure 1.22 donne une représentation plus compacte.

Pour un dictionnaire de Scrabble anglais, la représentation par automate réduit la mémoire nécessaire d'environ 80 % par rapport à l'arbre.

Recherche d'information

La recherche d'une chaîne u dans un texte revient à tester si le texte appartient au langage A* u A*, qui est rationnel. On construit l'automate minimal de ce langage et on vérifie l'appartenance.

Pour un mot u de longueur n, un automate non déterministe à n+1 états peut être construit, et l'automate minimal possède aussi n+1 états.

Autres applications

Les automates séquentiels sont utilisés en traitement d'images pour la compression et les transformations (rotation, translation, homothétie). En théorie du contrôle, certains algorithmes sont basés sur les automates. En théorie des jeux, des stratégies peuvent être modélisées par des automates finis, permettant des algorithmes efficaces.

Extensions de la notion d'automate

Automates et mots infinis

Les automates ont été étendus aux mots infinis. Un automate de Büchi accepte un mot infini s'il existe un chemin infini partant d'un état initial et passant infiniment souvent par un état final.

Exemple : L'automate de la figure 1.23 accepte les mots infinis commençant par "a" et contenant une infinité de "b".

Le théorème de Kleene s'étend aux mots infinis avec des expressions rationnelles adaptées. Cependant, un automate de Büchi non déterministe n'est pas toujours équivalent à un automate déterministe. Pour rétablir l'équivalence, on utilise les automates de Muller, où l'acceptation dépend d'une table d'ensembles d'états visités infiniment souvent.

Exemple : L'automate de Muller de la figure 1.24 avec table {{2}} accepte les mots infinis visitant l'état 2 infiniment souvent et l'état 1 un nombre fini de fois, soit les mots contenant un nombre fini de "a". Avec la table {{1, 2}}, il accepte les mots infinis visitant à la fois 1 et 2 infiniment souvent.

Glossaire des termes clés

• Automate déterministe : Automate avec un seul état initial et au plus une transition par lettre depuis chaque état.
• Automate non déterministe : Automate pouvant avoir plusieurs états initiaux et plusieurs transitions identiques depuis un état.
• Automate séquentiel : Automate déterministe produisant un mot de sortie en fonction du mot d'entrée.
• Automate de Mealy : Automate séquentiel lettre à lettre avec sorties sur les transitions et états initiaux/finaux étiquetés par ε.
• Automate de Moore : Automate séquentiel avec sorties associées aux états.
• Automate minimal : Automate déterministe réduit au plus petit nombre d'états reconnaissant un langage donné.
• Langage reconnaissable : Langage reconnu par un automate déterministe.
• Langage rationnel (régulier) : Langage décrit par une expression rationnelle.
• Expression rationnelle : Expression algébrique utilisant union (+), produit (concaténation) et étoile (*) pour décrire un langage.
• Mot vide (ε) : Mot de longueur zéro.
• Concaténation : Opération consistant à joindre deux mots bout à bout.
• Automate de Büchi : Automate pour mots infinis, acceptant si un état final est visité infiniment souvent.
• Automate de Muller : Automate pour mots infinis avec acceptation basée sur une table d'ensembles d'états visités infiniment souvent.

Points clés à retenir

• Les automates finis sont le modèle le plus simple de machine capable de reconnaître des langages rationnels.
• Le théorème de Kleene établit l'équivalence entre langages rationnels et langages reconnaissables par automates.
• Les automates non déterministes sont équivalents aux automates déterministes, mais peuvent être plus compacts.
• Les automates séquentiels produisent des sorties et réalisent des fonctions telles que l'addition ou la multiplication par une constante.
• Les automates sont largement utilisés en informatique, linguistique, traitement d'images, vérification de systèmes et industries de la langue.
• Les automates ont été étendus aux mots infinis, avec des modèles spécifiques comme les automates de Büchi et de Muller.