AnalyseNotion · Glossaire
automate
En mathématiques et en informatique théorique, un automate est la formalisation abstraite d'un processus de calcul ou de transformation décrit comme une suite d'étapes élémentaires à partir d'un état initial. Une exécution peut être finie et aboutir à un dernier état, ou être infinie et ne pas avoir de dernier état. Pour un automate qui lit des mots, la description comprend notamment un ensemble d'états, un alphabet d'entrée, un mécanisme de transition, un état initial et un ensemble éventuellement vide d'états acceptants ; selon le modèle, la transition peut déterminer un unique état suivant ou en autoriser plusieurs. La théorie des automates constitue un outil fondamental pour l'étude des langages formels et la conception des algorithmes.
Sommaire
Ce que vous allez apprendre
- Identifier les composants d’un automate et le rôle de sa fonction de transition.
- Suivre le mot 1101 état par état jusqu’au verdict d’acceptation.
- Distinguer automate déterministe, modèles plus généraux, algorithme et automate mécanique.
- Éviter de conclure avant la dernière lecture ou d’appliquer aux parcours infinis le verdict des mots finis.
En clair
Imaginez une machine qui lit le mot binaire 1101, un symbole après l’autre. Elle ne garde pas tout le mot en mémoire : après chaque 0 ou 1, elle change d’état. Chaque état résume l’information que cette machine a été construite pour retenir en vue de la décision finale.
Si la machine est construite pour reconnaître les mots terminés par 01, elle accepte 1101. Les états, les symboles autorisés et les règles de passage forment un automate : une description abstraite qui transforme une entrée par étapes.
Définition
Un automate formalise un calcul ou une transformation comme un parcours entre des états. Pour un automate qui lit des mots, sa description comprend notamment un ensemble d’états, un alphabet d’entrée, un état initial, un ensemble éventuellement vide d’états acceptants et un mécanisme de transition. L’alphabet indique les symboles lisibles. Selon le modèle, les transitions déterminent un unique nouvel état ou autorisent plusieurs états possibles après la lecture d’un symbole.
Dans un automate déterministe, si l’état courant est noté q, si le symbole lu est noté a, si l’état suivant est noté q’ et si la fonction de transition est notée par la lettre grecque delta, la règle s’écrit . Pour un mot fini, on part de l’état initial et on applique cette règle symbole après symbole. Le mot est accepté lorsque l’état atteint après la dernière lecture est acceptant. L’ensemble des mots acceptés constitue le langage reconnu.
Tous les automates ne sont ni finis ni déterministes. Selon le modèle, l’ensemble d’états ou le nombre d’étapes peut être infini, et plusieurs transitions peuvent être possibles. Cette abstraction sert à étudier les langages formels et à concevoir des algorithmes.
Un exemple, pas à pas
Construisons un automate déterministe qui accepte exactement les mots binaires terminés par 01. L’alphabet contient 0 et 1. L’état initial q0 signifie qu’aucun suffixe utile n’est mémorisé ; q1 signifie que le dernier symbole est 0 ; l’état acceptant q2 signifie que le suffixe courant est 01. Les transitions sont les suivantes : depuis q0, 0 mène à q1 et 1 à q0 ; depuis q1, 0 mène à q1 et 1 à q2 ; depuis q2, 0 mène à q1 et 1 à q0. Le mot testé est 1101. La figure matérialise les quatre lectures successives.
1. Le premier 1 laisse l’automate en q0.
2. Le deuxième 1 le laisse encore en q0.
3. Le 0 conduit de q0 à q1.
4. Le dernier 1 conduit de q1 à q2. La lecture s’achève dans l’état acceptant : 1101 est donc accepté. Pour contrôler la règle, le mot 110 se termine en q1 et est refusé, conformément au suffixe recherché.
En pratique
Pour tester l’appartenance à un langage formel, on encode les symboles autorisés et les passages entre états, puis on lit le mot jusqu’au dernier symbole. Si le critère dépend seulement d’un motif fixe très court, un test direct peut être plus simple ; l’automate devient utile quand la même règle doit traiter de nombreux mots.
Pour décrire un algorithme par étapes, chaque état résume l’information nécessaire à la suite du calcul. Une description ordinaire convient si l’ordre des opérations suffit ; l’automate est préférable lorsque les possibilités futures dépendent explicitement de l’état atteint.
Pour vérifier une transformation, on suit une entrée précise et on note chaque transition. Le parcours obtenu rend contrôlables l’état de départ, les choix successifs et le verdict final.
À ne pas confondre
Un automate et un algorithme. Un automate décrit un calcul par des états et des transitions ; un algorithme décrit une procédure à exécuter. Dans l’exemple de 1101, le tableau des transitions définit l’automate, tandis que la lecture successive des quatre symboles constitue une procédure d’exécution.
Un automate abstrait et un automate mécanique. Le premier est un modèle mathématique défini par des états, un alphabet et des transitions. Le second est un objet matériel qui produit des mouvements. La présence d’engrenages ou d’un mécanisme physique tranche le cas ; elle n’est pas requise pour l’objet étudié ici.
Limites et pièges
Atteindre un état acceptant trop tôt. Pour un mot fini, le verdict dépend de l’état atteint après le dernier symbole. Avec l’automate de l’exemple, 011 atteint q2 après 01, puis revient en q0 après le dernier 1 : le mot est refusé. Il faut donc achever la lecture avant de conclure.
Supposer que tout automate est fini. Le mot « automate » ne garantit ni un nombre fini d’états ni un nombre fini d’étapes. Il faut vérifier le modèle employé avant d’appliquer une propriété réservée aux automates finis.
Supposer une transition unique. L’exemple est déterministe : une paire formée d’un état et d’un symbole impose un seul état suivant. D’autres modèles autorisent plusieurs évolutions possibles. Il faut alors étudier les parcours permis plutôt que choisir arbitrairement une branche.
Transposer sans précaution le verdict des mots finis. Une exécution infinie ne possède pas de dernière lecture. La simple règle « finir dans un état acceptant » ne suffit donc pas ; le modèle doit préciser une condition d’acceptation adaptée aux parcours infinis.
Pour aller plus loin
L’article Langages formels et automates approfondit la relation entre les mots, les règles de formation et les machines qui les reconnaissent.
La fiche algorithme précise l’autre grande notion mobilisée lorsqu’un automate sert à formaliser un processus de calcul.
La fiche machine de Turing ouvre sur un modèle de calcul plus riche et permet de situer les automates dans l’informatique théorique.
Explorez les mathématiques autrement
Retrouvez nos magazines, podcasts et jeux pour explorer les mathématiques autrement.
Découvrir les offres