Théorie des automates

En informatique théorique, l'objectif de la théorie des automates est de proposer des modèles de mécanismes mathématiques qui formalisent les méthodes de calcul^[1]. Cette théorie est le fondement de plusieurs branches importantes de l'informatique théorique, comme :

• La calculabilité, par le modèle des machines de Turing ;
• Les automates finis, et leurs variantes, qui sont utilisés dans l'analyse des langues naturelles, la traduction des programmes par les compilateurs, divers algorithmes de manipulation de textes comme les algorithmes de recherche de sous-chaîne, ou la vérification automatique du fonctionnement de circuits logiques;
• La théorie de la complexité des algorithmes, visant à classifier les algorithmes en fonction des ressources temporelles et en mémoire nécessaires à leur exécution ;
• La vérification de modèle qui sert à établir la conformité de programmes à leurs spécifications. Voir par exemple Coq.

Les automates n'ont pas d'existence physique, mais sont un modèle abstrait.

Une façon de voir une machine de Turing.

Concepts fondamentaux de la théorie des automates

Alphabet

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.

Mots ou chaînes

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^{*}}$.

Langage formel

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\}.}$

Objectif

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.

Caractéristiques communes des automates

Il existe de très nombreux modèles d'automates. Les caractéristiques communes aux automates sont les suivantes (avec des variantes possibles) :

• Un automate prend en entrée des données discrètes (même si certains automates, appelés automates temporisés, ont des paramètres qui peuvent être des nombres réels). Ces entrées sont généralement des mots finis sur un alphabet fini, mais ce sont aussi des mots infinis, des arbres, des graphes, ou des structures encore plus compliquées.
• Un automate possède un nombre fini de configurations internes, appelées états. Là aussi, on peut considérer des automates ayant un nombre infini d'états : par exemple, dans la théorie générale des automates, tout langage formel possède un automate minimal unique, qui n'est fini que si le langage est rationnel. Les systèmes de transitions utilisés en model checking n'ont pas de contrainte sur le nombre d'états.
• Un automate peut disposer, par ailleurs, d'une mémoire auxiliaire externe, structurée d'une certaine façon selon le type d'automate. Un automate fini n'a pas de mémoire auxiliaire, un automate à pile a une mémoire en pile ; il existe des automates à mémoire en structure de file, des automates à plusieurs piles, des automates à piles de pile, etc. Les machines de Turing ont une mémoire auxiliaire en forme de bande infinie sur laquelle elles peuvent se déplacer, lire et écrire.
• Un automate évolue selon des règles. Ces règles sont en nombre fini. Chaque règle décrit, en fonction des symboles d'entrée, de l'état, et d'une information sur la mémoire auxiliaire, l'évolution de l'automate. Cette évolution peut être déterministe ou non. Elle est déterministe si une seule règle est applicable dans une configuration donnée, elle est non déterministe sinon.
• Un automate possède un certain nombre de configurations d'acceptation. Si l'automate se trouve dans une telle configuration, la donnée lue est acceptée. Dans un automate fini, ces configurations sont des états distingués, dans un automate à pile, on peut accepter si la pile est vide, dans une machine de Turing, on accepte si l'état est acceptant.

Automates

Fig. 1 : Une hiérarchie d'automates.

Voici quelques familles d'automates.

Automates finis

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.

Automates sur les mots infinis

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.

Automates temporisés

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].

Automates probabilistes, automates quantiques

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.

Automates pondérés

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.

Automates bidirectionnels

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.

Automate alternant

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.

Automate séquentiel

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.

Automate de Parikh

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.

Modèles de Markov caché

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.

Systèmes de transitions, structure de Kripke

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.

Automates à pile

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.

Automates à file

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.

Automates à pile emboîtée, à pile visible, à pile de piles

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

Automates d'arbres

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.

Automates cheminant dans un arbre, à jetons

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.

Systèmes de réécriture

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.

Réseaux de Petri

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.

Automates linéairement bornés

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.

Machines de Turing

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é.

Références et bibliographie

Références

1. Hopcroft & Ullman (1979), page 1
2. Pour une introduction, voir par exemple l'article Timed automata.

Bibliographie

• 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)

Annexes

Articles connexes

• 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