Théorie des automates

Un alphabet est un ensemble quelconque. Ses éléments sont appelés lettres ou symboles. Les lettres n’ont pas de propriétés particulières. On demande seulement de savoir tester si deux lettres sont égales ou différentes.

Parmi les exemples d'alphabets, il y a bien sûr l’alphabet latin, et tous les alphabets des langues naturelles. Il y a aussi l’alphabet binaire, composé des symboles 0 et 1, l’alphabet hexadécimal, l’alphabet des acides aminés, etc. En informatique, on rencontre l’alphabet des lexèmes, c’est-à-dire des unités syntaxiques résultant de l’analyse lexicale d’un programme.

Un mot ou une chaîne sur un alphabet ${\displaystyle A}$ est une suite finie

${\displaystyle w=(a_{1},\ldots ,a_{n})}$

d'éléments de ${\displaystyle A}$. On écrit plutôt

${\displaystyle w=a_{1}\cdots a_{n}}$

L'entier ${\displaystyle n}$ est la longueur du mot. Il existe un seul mot de longueur 0, appelé le mot vide, et noté souvent ${\displaystyle \varepsilon }$. Le produit de concaténation de deux mots

${\displaystyle x=a_{1}\cdots a_{n}}$ et ${\displaystyle y=b_{1}\cdots b_{m}}$

est le mot

${\displaystyle xy=a_{1}\cdots a_{n}b_{1}\cdots b_{m}}$

obtenu par juxtaposition des deux mots. Le produit de concaténation est associatif, le mot vide est l'élément neutre pour cette opération, ce qui fait de l'ensemble des mots sur l'alphabet ${\displaystyle A}$ un monoïde. Ce monoïde est libre, et est noté ${\displaystyle A^{*}}$.

Un langage formel sur un alphabet ${\displaystyle A}$ est un ensemble de mots sur ${\displaystyle A}$, donc un sous-ensemble de ${\displaystyle A^{*}}$. Les opérations ensemblistes (union, intersection, complément) s'étendent bien entendu aux langages. Le produit de concaténation des mots s'étend aux langages de la manière suivante. Si ${\displaystyle X}$ et ${\displaystyle Y}$ sont deux langages sur ${\displaystyle A}$, leur produit est le langage

${\displaystyle XY=\{xy\mid x\in X,y\in Y\}.}$

Une autre opération est l'étoile de Kleene. Pour une partie ${\displaystyle X}$ de ${\displaystyle A^{*}}$, elle est notée ${\displaystyle X^{*}}$ et est définie par

${\displaystyle X^{*}=\{x_{1}x_{2}\cdots x_{n}\mid n\geq 1,x_{i}\in X\}.}$

La théorie des automates est l'étude des machines abstraites qui permettent de formaliser les méthodes de calcul. L'objet traité par un automate est un mot d'un langage. Pour arriver à la généralité souhaitée, on convertit un « problème » en un langage, et la résolution du problème, en l'analyse d'un élément de ce langage.

On représente chaque instance d'un « problème » par un mot. Savoir si l'instance du problème a une solution se ramène à tester si ce mot appartient au langage des mots représentant les instances de ce problème et qui ont une solution. Un automate qui résout le problème prend en entrée un mot et décide s'il est accepté ou non.

Par exemple, le problème de savoir si un entier N est premier (test de primalité) peut se traduire comme suit : on représente tous les entiers naturels par des chaînes binaires (écriture en base 2). Dans ce langage, les mots représentant des nombres premiers forment un sous-ensemble. Le problème du test de primalité consiste alors à savoir si la chaîne binaire représentant un nombre N appartient à ce sous-ensemble ou non. Un automate approprié prend en entrée une chaîne binaire et l'accepte précisément lorsqu'elle représente un nombre premier.

La formulation des problèmes et de leur résolution (ou même de leur calculabilité) en termes de langage formels est à la base des hiérarchies de complexité, et des hiérarchies des langages formels.

Un autre domaine concerne la transformation de mots. Dans ce domaine, on utilise plutôt le terme de « machine » ou de transducteur. La linguistique, mais aussi la compilation, font usage de tels transducteurs pour l'analyse et la transformation de textes ou de programmes.

Les automates finis constituent la classe la plus simple d'automates. Ils reconnaissent exactement les langages rationnels (ou réguliers). Ils sont appliqués dans de nombreux domaines, et possèdent plusieurs caractérisations, combinatoires et algébriques.

Les automates finis ont été étendus aux mots infinis. Plusieurs modèles d'automate ont été introduits et comparés. Les plus connus sont les automates de Büchi et de Muller. On connaît des caractérisations des ensembles de mots infinis reconnus par ces automates. La plus grande difficulté réside dans le fait que les notions d'automate déterministe et non déterministe ne sont plus équivalentes.

Les automates temporisés (en anglais timed automata) ont des contraintes sur les transitions qui s'expriment par des conditions sur la durée[2].

Les automates probabilistes ont été introduits très tôt (en 1963) par Michael O. Rabin. Chaque transition porte une probabilité ; les probabilités se multiplient sur les chemins, et pour qu'un mot soit accepté, il faut que la somme des probabilités sur les chemins atteigne un certain seuil. Ces automates ont été repris et étendus, dans une optique différente, par les automates quantiques.

Ces automates sont plus généraux que les automates probabilistes. Leurs transitions portent un élément d'un demi-anneau quelconque. Les automates pondérés servent par exemple dans l'énumération de structures combinatoires, ou pour modéliser la multiplicité de reconnaissance ou l’ambiguïté de génération de mots dans un automate fini.

Un tel automate peut lire le mot d'entrée de la gauche vers la droite ou revenir, de la droite vers la gauche. Aussi appelé « boustrophédon » par référence au système d'écriture, un automate fini bidirectionnel ne reconnaît pas plus de langages qu'un automate fini usuel. Pour les transducteurs finis, la situation est plus complexe.

Cette variation des automates finis non déterministe définit une classe qui est d'un emploi plus souple pour la spécification de programmes, dans le cadre du model checking. Un automate fini alternant peut varier son mode d'acceptation en sélectionnant les chemins à parcourir, et en combinant les résultats par des formules booléennes.

Un automate séquentiel est un automate fini avec sortie qui est déterministe en entrée. Les fonctions calculées par les automates séquentiels sont appelées fonctions séquentielles. Même si elles n'ont pas la puissance des transductions fonctionnelles, elles permettent de réaliser des opérations comme l’addition de deux entiers, la division euclidienne d'un polynôme à coefficients dans un corps fini par un polynôme donné, et trouvent aussi des emplois en linguistique formelle.

Un automate de Parikh est un automate fini non déterministe dont les transitions comportent des vecteurs d’entiers naturels qui permettent de tester si la somme des vecteurs d'un calcul satisfait une contrainte semi-linéaire. L'intérêt de cette famille d'automates est qu'elle possède d'autres caractérisations équivalentes, sous forme de machine de Turing particulière et sous une forme plus algébrique, dite RCM.

Un modèle de Markov caché (MMC) — en anglais « Hidden Markov Models » (HMM) — (ou plus correctement automate de Markov à états cachés mais ce terme n'est pas employé) est un modèle statistique dans lequel le système modélisé est supposé être un processus markovien de paramètres inconnus. Les modèles de Markov cachés sont massivement utilisés notamment en reconnaissance de formes, en intelligence artificielle ou encore en traitement automatique du langage naturel.

Les systèmes de transition d'états sont une extension des automates finis à des ensembles éventuellement infinis, et sans tenir compte des conditions d'acceptation. Dans leur version la plus rudimentaire, ce sont simplement des relations binaires. Dans une version plus élaboré, ce sont des automates sans état initial et sans états terminaux. Les versions les plus complexes sont les structures de Kripke qui portent, associées aux états, des formules logiques.

Les automates à pile reconnaissent exactement les langages algébriques. Le concept de pile, formalisé dans ces automates, a une portée dans de nombreux domaines, comme dans la programmation (avec la récursivité), l'analyse syntaxique, comme structure de données fondamentale. Là aussi, les automates à pile déterministe sont plus restreints que les automates généraux.

Les automates à file opèrent comme les automates à pile, mais utilisent comme mémoire auxiliaire une file (first in, first out) à la place d’une pile. Leurs puissance de reconnaissance est toute différente puisqu’ils sont équivalents aux machines de Turing.

De nombreuses variantes étendant les automates à pile sont étudiés, en liaison avec les graphes infinis, et la théorie des jeux.

Les automates finis ont été très tôt étendus aux arbres ; on distingue essentiellement les automates ascendants, qui reconnaissent les arbres en partant des feuilles et en remontant vers la racine (un peu comme dans l'évaluation des expressions arithmétiques), et les automates descendants qui opèrent dans le sens inverse. Les deux concepts sont équivalents dans le cas non déterministe. D'autres types d'automates d'arbres ont été définis, parmi lesquels les automates cheminant.

Les automates cheminant ont été introduits en 1971. Ce sont des automates finis qui cheminent dans un arbre de manière séquentielle. Les automates à jetons sont une extension des automates cheminant. Ils sont moins puissant que les automates d'arbres.

Un langage congruentiel est un langage formel qui est réunion d'un nombre fini de classes d'une congruence sur l'alphabet donné. Un cas important est celui où la congruence engendrée par un système de réécriture de mots fini. Selon le type du système de réécriture, la complexité algorithmique du problème du mot peut être linéaire en temps, PSPACE-complet ou indécidable. Les classes de langages congruentiels forment une autre hiérarchie de langages, incomparable à la hiérarchie de Chomsky.

Ces automates prennent bien en compte la possibilité d'exécuter des opérations dans un ordre indifférent. Ils sont utilisés dans la modélisation de processus.

Ces automates reconnaissent exactement les langages contextuels. Ils permettent de rendre compte de certaines contraintes portant sur le contexte dans les langues naturelles, mais en linguistique, des langages et des automates plus contraints, comme les grammaires d'arbres adjoints se sont avérés plus maniables.

Tout en haut de la hiérarchie des automates se situent les machines de Turing. Introduites par Turing en 1937, elles reconnaissent exactement les langages récursivement énumérables. Ces langages, et les machines de Turing, sont utilisés comme définition mathématique de ce qui est calculable. Plusieurs autres caractérisations équivalentes sont connues. La thèse de Church (qui n'est pas un énoncé mathématique, mais une simple affirmation) dit que cette définition mathématique reflète correctement ce que le « bon sens » peut considérer comme calculable par un esprit humain. La hiérarchie de Chomsky connaît quatre types de grammaires et de langages : récursivement énumérable (type 0), contextuel (type 1), algébrique (type 2), rationnel (type 3).

Les machines de Turing et leurs variantes ont donné naissance à une hiérarchie de classes de complexité foisonnante et riche, qui cherche à classer les problèmes d'algorithmique selon leur difficulté.

• John E. Hopcroft et Jeffrey D. Ullman, Introduction to Automata Theory, Languages and Computation, Addison-Wesley, 1979
• Daniel I. A. Cohen, Introduction to Computer Theory, John Wiley & Sons, 1997
• Michael A. Harrison, Introduction to Formal Language Theory, Addison-Wesley, 1978

• J. C. Martin, Introduction to Languages and the Theory of Computation,, McGraw-Hill, 1997, second edition
• Jacques Sakarovitch, Éléments de théorie des automates, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5)
  Traduction anglaise avec corrections : Elements of Automata Theory, Cambridge University Press 2009, (ISBN 9780521844253)

• Olivier Carton, Langages formels, calculabilité et complexité : licence et master de mathématiques ou d'informatique, option informatique de l'agrégation de mathématiques, Paris, Vuibert, 2008, 237 p. (ISBN 978-2-7117-2077-4)

• Pierre Simonnet, Automates et théorie descriptive, Université Paris-Diderot, 1992

• Yliès Falcone et Jean-Claude Fernandez, Automates à états finis et langages réguliers : Rappels des notions essentielles et plus de 170 exercices corrigés, Grenoble, Dunod, 2020, 320 p. (ISBN 978-2100808465)

• Grammaire formelle
• Hiérarchie de Chomsky
• Théorie de la complexité des algorithmes
• Théorie de la calculabilité
• Automate fini déterministe
• Automate fini non déterministe