Théorie des automates

Pour les articles homonymes, voir Théorie et Automate.

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. C'est la partie sur laquelle on insiste le plus dans les écoles d'ingénieurs, car elle est immédiatement exploitable avec profit ;
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 $A$ est une suite finie

w=(a_1,\ldots,a_n)

d'éléments de $A$ . On écrit plutôt

w=a_1\cdots a_n

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

x=a_1\cdots a_n

y=b_1\cdots b_m

est le mot

xy=a_1\cdots a_nb_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 $A$ un monoïde. Ce monoïde est libre, et est noté $A^*$ .

Langage formel

Un langage formel sur un alphabet $A$ est un ensemble de mots sur $A$ , donc un sous-ensemble de $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 $X$ et $Y$ sont deux langages sur $A$ , leur produit est le langage

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

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

X^*=\{x_1x_2\cdots x_n\mid n\ge0,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 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érales 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

Voici une liste d'automates.

Automates finis

Article détaillé : Automate fini.

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

Articles détaillés : Automate sur les mots infinis, Automate de Büchi et Automate de Muller.

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

Articles détaillés : Automate probabiliste, Automate quantique (en)

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.

Systèmes de transitions, structure de Kripke

Articles détaillés : Système de transition d'états et 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

Article détaillé : Automate à 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 à pile emboîtée, à pile visible, à pile de piles

Articles détaillés : Automate à pile emboîtée (en), Automate à pile visible (en)

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

Article détaillé : Automate 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.

Automates cheminant dans un arbre, à jetons

Articles détaillés : Automate cheminant (en), Automate à jetons (en)

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.

Réseaux de Petri

Article détaillé : Réseau 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

Article détaillé : Automate linéairement borné.

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

Article détaillé : Machine de Turing.

Tout en haut de la hiérarchie des automates se situent les machines de Turing. Introduites par Turing en 1937, ils 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

↑ Hopcroft & Ullman (1979), page 1
↑ 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 (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é, Vuibert,‎ 2008 (ISBN 978-2-7117-2077-4)

Articles connexes

Grammaire formelle
Hiérarchie de Chomsky
Théorie de la complexité des algorithmes
Théorie de la calculabilité
Théorie des automates finis

Portail de l’informatique
Portail de la logique
Portail de la linguistique
Portail de l'informatique théorique

This article is issued from Wikipédia - version of the Wednesday, July 08, 2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.