Automate fini

Fig. 2 : Diagramme d'état d'un portillon.

Un portillon.

Un exemple très simple d'un mécanisme que l'on peut modéliser par un automate fini est un portillon d'accès[1]^,[2]. Un portillon, utilisé dans certains métros ou dans d'autres établissements à accès contrôlés, est une barrière avec trois bras rotatifs à hauteur de la taille. Au début, les bras sont verrouillés et bloquent l'entrée, et empêchent les usagers de passer. L'introduction d'une pièce de monnaie ou d'un jeton dans une fente du portillon (ou la présentation d'un ticket ou d'une carte) débloque les bras et permet le passage d'un et un seul usager à la fois. Une fois l'usager entré, les bras sont à nouveau bloqués jusqu'à ce qu'un nouveau jeton soit inséré.

Un portillon, vu comme un automate fini, a deux états : verrouillé (« locked » en anglais) et déverrouillé (« unlocked » en anglais)[1]. Deux « entrées » peuvent modifier l'état : la première si l'on insère un jeton dans la fente (entrée jeton) et la deuxième si l'on pousse le bras (entrée pousser). Dans l'état verrouillé, l'action de pousser n'a aucun effet : quel que soit le nombre de fois que l'on pousse, l'automate reste verrouillé. Si l'on insère un jeton, c'est-à-dire si l'on effectue une « entrée » jeton, on passe de l'état verrouillé à l'état déverrouillé. Dans l'état déverrouillé, ajouter des jetons supplémentaires n'a pas d'effet, et ne change pas l'état. Mais dès qu'un usager tourne le bras du portillon, donc fournit un pousser, la machine retourne à l'état verrouillé.

L'automate d'un portillon peut être représenté par une table de transition d'états qui montre, pour chaque état, le nouvel état et la sortie (l'action) pour une entrée donnée.

État courant	Entrée	État suivant	Sortie
verrouillé	jeton	déverrouillé	Déverrouille le portillon pour qu'un usager puisse passer
	pousser	verrouillé	Rien
déverrouillé	jeton	déverrouillé	Rien
	pousser	verrouillé	Quand l'usager est passé, verrouille le portillon

On peut aussi représenter l'automate par un graphe orienté, appelé un diagramme états-transitions, comme donné ci-dessus. Chaque état est représenté par un sommet (visualisé par un cercle). Les arcs (représentés par des flèches) montrent les transitions d'un état à un autre. Chaque flèche porte une entrée qui déclenche la transition. Les données qui ne provoquent pas de changement d'état, comme un jeton pour l'état déverrouillé, sont représentées par des arcs circulaires (des boucles) qui tournent autour de l’état. La flèche qui entre dans l'état verrouillé depuis le point noir sert à indiquer que cet état est l'état initial, au début de la modélisation.

Le loup, la chèvre et le chou. Chaque état représente ce que le passeur a déjà transporté (le chou est noté « S »).

L'exemple que voici[3] illustre les possibilités qui s'offrent à un passeur qui doit faire traverser, d'une rive à l'autre, un loup, une chèvre et un chou (c'est une variante des nombreux problèmes de passage de rivière). Sa barque ne lui permet que d'emporter un seul des trois objets à la fois et, bien entendu, il ne peut laisser ensemble loup et chèvre ni chèvre et chou. Dans le diagramme ci-contre, un état représente ce que le passeur a déjà pu transporter sur l’autre rive (« P » représente le passeur, « L » le loup, « C » la chèvre, et le chou a été noté par « S ») : au début rien, à la fin tout. Sur les flèches, les objets transportés (et lui-même). Une des deux séquences de transport est CPLCSPC, l'autre est CPSCLPC. Bien entendu, on néglige les aller-retour-aller inutiles.

Plusieurs types de tables de transition d'état sont utilisées. Ces diagrammes sont très populaires en UML notamment. La représentation la plus courante est illustrée ci-dessous ; la combinaison de l'état courant (par exemple B) et d'une entrée (par exemple Y) montre l'état suivant (dans l’exemple C). L'information complète associée à une action n'est pas décrite dans la table et peut être ajoutée par des annotations. Une définition d'une machine finie avec actions est possible au moyen de tables de transition dans le modèle plus élaboré d'automate fini virtuel (en)[4].

Table de transitions

Entrée État	Entrée X	Entrée Y	Entrée Z
État A	…	…	…
État B	…	État C	…
État C	…	…	…

Exemple de diagramme UML de fonctionnement d'un four.

Le langage de spécification Unified Modeling Language (UML) a une notation propre pour décrire des automates. Ce sont des diagrammes comportementaux particuliers qui permettent de dépasser les limitations de machines finies traditionnelles tout en conservant leurs avantages principaux. Les machines ou automates UML introduisent les notions nouvelles de diagramme de structure composite, d'états hiérarchiques et d'agrégation, tout en étendant la notion d'action. Les machines finies UML ont à la fois les propriétés des machines de Mealy et des machines de Moore décrites plus bas. Elles supportent des actions qui dépendent à la fois de l'état du système et de l'événement déclenchant, comme dans les machines de Mealy, et aussi des actions d'entrée et de sortie associées à des états, comme dans les machines de Moore.

Exemple d'une machine finie en SDL.

Fig. 3 : Exemple d'un automate fini à deux états.

Le langage de spécification et de description appelé Specification and Description Language ou SDL est une norme élaborée par l'Union internationale des télécommunications (UIT)[5]. La norme contient un ensemble de symboles graphiques permettant de décrire les actions dans une transition :

• envoi d'un message ;
• réception d'un message ;
• démarrage d'un temporisateur (timer) ;
• arrêt d'un temporisateur ;
• lancement d'une machine concurrente ;
• prise de décision.

Un SDL contient des types de base, mais surtout des types de données abstraits (TDA) et une syntaxe de manipulation qui permet de décrire le système de manière formelle, possiblement de manière complète et non ambiguë.

Il existe de nombreuses variantes de diagrammes d'états-transitions, comme le diagramme d'un automate à deux états donné plus haut.

Fig. 4 : Automate accepteur : analyse du mot « nice ».

Les accepteurs, également appelés reconnaisseurs produisent une sortie binaire, indiquant si l'entrée reçue est acceptée ou non. Chaque état d'un tel automate est soit un état d'acceptation, aussi appelé final ou terminal, ou un état de rejet. Si l'état courant, après la lecture de la totalité de l'entrée, est un état d'acceptation, l'entrée est acceptée, sinon elle est rejetée. L'entrée est généralement une suite de symboles (des lettres); il n'y a pas d'actions associées. L'exemple de la figure 4 montre un automate fini qui accepte le mot « nice ». Dans cet automate, seul l'état 7 est acceptant.

Une machine peut aussi être décrite comme définissant un langage formel. Ce langage est composé des mots acceptés par la machine, et d'aucun mot rejeté par elle. Par définition, les langages acceptés par un automate fini sont appelés les langages reconnaissables. Par le théorème de Kleene, ce sont les langages réguliers ou rationnels, décrits par des expressions régulières ou rationnelles.

Le problème de déterminer le langage accepté par un automate fini donné est une instance d'un problème plus général appelé le problème algébrique de cheminement (« algebraic path problem »), qui lui-même est une extension des problèmes de cheminement dans des graphes dont les arcs portent des poids pris dans un demi-anneau arbitraire[8]^,[9].

L'état initial est en général indiqué en traçant une flèche qui pointe vers cet état « à partir de n'importe où »[10].

Fig. 5 : Représentation d'un automate fini qui détermine si une suite binaire contient un nombre pair de 0. L'état ${\displaystyle S_{1}}$ est final.

Un état d'acceptation (aussi appelé état acceptant, final ou terminal) est un état dans lequel la machine déclare que la chaîne d'entrée traitée jusqu'alors appartient au langage qu'elle reconnaît. Graphiquement les états d'acceptation sont fréquemment représentés par des cercles doublés. Une autre façon, symétrique à celle adoptée pour l'état initial, consiste à faire sortir une flèche « pointant vers nulle part » d'un tel état[3].

L'état initial peut aussi être un état final ; dans ce cas, l'automate accepte la chaîne vide. Si l'état initial n'est pas un état d'acceptation, et s'il n'existe pas d'arc vers un état final, l'automate n'accepte aucun mot.

La figure 5 est l'exemple d'un automate fini déterministe. Cette automate accepte les suites binaires qui comportent un nombre pair de chiffres 0. L'état S₁ est à la fois l'état initial et l'état terminal. L'automate termine dans l'état S₁ si la chaîne lue contient un nombre pair (éventuellement nul) de 0 : chaque 0 fait basculer d'un état vers l'autre, alors qu'un 1 laisse l'état inchangé. Des exemples de chaînes acceptées sont ε , le mot vide, puis 1, 11, 11…, 00, 010, 1010, 10110, etc.

Fig. 6 : Automate transducteur : modèle de Moore.

Les transducteurs finis génèrent en sortie des mots en fonction d'un mot d'entrée donné et d'actions associées aux états. Ils sont utilisés par exemple dans des applications de contrôle et dans le domaine de la linguistique informatique. On distingue deux types de transducteurs, les machines de Moore et les machines de Mealy. Elles diffèrent par les modalités qui déterminent les sorties. On peut démontrer qu'elles ont la même puissance d'expression.

Machine de Moore

Dans le modèle de Moore, qui utilise seulement des actions d'entrée, la sortie dépend uniquement de l’état courant. Comparé au modèle de Mealy, le modèle de Moore a l'avantage de la simplicité et de facilité de compréhension. Considérons par exemple une porte d'ascenseur, modélisée par une machine qui reconnaît deux commandes : « ouvrir » et « fermer », commandes qui peuvent être données par un utilisateur. L'action d'entrée (E:) dans l'état d'« en cours d'ouverture » fait démarrer un moteur qui ouvre la porte, et dans l'état « en cours de fermeture » fait démarrer un moteur qui ferme la porte. Les états « ouvert » et « fermé » arrêtent le moteur quand la porte est entièrement ouverte ou entièrement fermée. Ils signalent par ailleurs cette situation vers l’extérieur par « porte ouverte » ou « porte fermée ».

Fig. 7 : Transducteur : modèle de Mealy.

Machine de Mealy

Dans le modèle de Mealy, qui utilise également des actions d'entrée, la sortie dépend à la fois de l'entrée et de l'état. L'usage de machines de Mealy réduit souvent le nombre d'états. En contrepartie, le fonctionnement d'un automate est plus complexe et plus difficile à appréhender. La figure 7 montre un automate de Mealy qui a le même comportement que l’automate de Moore. Il y a deux actions d'entrée (I:): « démarrer le moteur pour fermer la porte quand la commande de fermeture arrive », et la commande symétrique pour l'ouverture. Les états intermédiaires « en cours d'ouverture » et « en cours de fermeture » ne sont pas nécessaires.

Les variantes suivantes sont d'un emploi assez rare. Un classificateur est similaire à un accepteur, mais possède au moins deux états terminaux. Un tel automate peut donc accepter plusieurs langages simultanément, selon la catégorie d'états à laquelle appartient l'état terminal atteint en fin de lecture. Un séquenceur ou générateur est un cas particulier d'automate, opérant sur un alphabet d'entrée à une seule lettre. Un tel automate produit une seule séquence qui peut être interprétée comme le résultat d'un transducteur ou d'un classificateur.

Un automate fini avec un état unique est appelé parfois « combinatoire » ; il utilise uniquement des actions d'entrée. Cette notion peut servir lorsque plusieurs automates finis sont censés travailler de concert, en communiquant ; il peut alors être commode de considérer des automates combinatoires comme une brique dans un outil de conception[11].

Une distinction supplémentaire importante est celle entre automates finis déterministes et non déterministes. Dans un automate déterministe, chaque état possède au plus une transition pour chaque symbole d'entrée (et même exactement une dans le cas où l'automate est complet). Dans un automate non déterministe, un symbole d'entrée peut étiqueter une, plusieurs ou aucune transition pour un état donné. Cette distinction est importante en pratique, mais moins en théorie parce qu'il existe un algorithme (la construction par sous-ensembles) qui permet de transformer un automate fini non déterministe en un automate fini déterministe avec la même fonctionnalité. Toutefois, et c'est là un biais qui peut entraver l'efficacité, l'algorithme de construction par sous-ensembles peut produire un automate dont la taille est exponentielle par rapport à la taille de l'automate de départ. C'est pourquoi certains algorithmes (comme le programme grep de Unix) tentent des compromis.

Le schéma électrique pour un compteur TTL à 4 bits.

En électronique numérique, un automate fini peut être construit comme circuit logique programmable, ou un automate programmable industriel, avec des fonctions logiques réalisées par bascules ou relais. Une implémentation matérielle demande en général un registre pour stocker les variables d'état, un circuit de logique combinatoire qui détermine les transitions d'états, et un deuxième bloc de logique combinatoire qui détermine les sorties de l'automate. Une implémentation courante est le Richards controller (en).

Un cas particulier des automates de Moore, où la sortie est directement connectée aux états, est connu sous le nom d'automate de Medvedev[20]. Il est par ailleurs recommandé, dans la conception de chips, de ne pas placer de circuit logique entre les entrées-sorties primaires et les registres, afin de minimiser les délais entre chips qui sont habituellement longs et ralentissent la fréquence des automates. On peut aussi optimiser les automates en vue de minimiser la consommation d'énergie par des techniques spécifiques (en).

Les concepts suivants sont fréquemment employés dans la construction d'applications utilisant des automates finis :

• Programmation fondée sur des automates (en)
• Automate fini dirigé par événements (en)
• Automate fini virtuel (en)
• État (patron de conception)

Les automates finis sont souvent utilisés au début du processus de compilation dans les compilateurs de langages de programmation. Une telle entité peut comporter plusieurs automates finis, qui implémentent l'analyse lexicale.

Partant d'une séquence de caractères, un analyseur lexical construit une suite de lexèmes, tels que les mots réservés, les identificateurs, les littéraux ; à partir de cette suite, l'analyseur syntaxique construit l'arbre syntaxique. L'analyseur lexical et l'analyseur syntaxique gèrent la partie régulière et algébrique de la grammaire d'un langage de programmation[21].

• Ferdinand Wagner, Ruedi Schmuki, Thomas Wagner et Peter Wolstenholme, Modeling Software with Finite State Machines : A Practical Approach, Auerbach Publications, 2006, 392 p. (ISBN 978-0-8493-8086-0).
• Christos G. Cassandras et Stéphane Lafortune, Introduction to Discrete Event Systems, Springer Science & Business Media, 1999, 822 p. (ISBN 978-0-7923-8609-4, présentation en ligne).
• Timothy Kam, Tiziano Villa, Robert K. Brayton et Alberto Sangiovanni-Vincentelli, Synthesis of Finite State Machines : Functional Optimization, Springer, 1996, 282 p. (ISBN 978-0-7923-9842-4, présentation en ligne)
• Timothy Kam, Tiziano Villa, Robert K. Brayton et Alberto Sangiovanni-Vincentelli, Synthesis of Finite State Machines : Logic Optimization, Springer, 1997, 381 p. (ISBN 978-0-7923-9892-9)
• Yishai A. Feldman, « Finite-state Machines », dans Allen Kent et James G. Williams (éditeurs), Encyclopedia of Computer Science and Technology : Volume 25 - Supplement 10, Marcel Dekker, 1992 (ISBN 0-8247-2275-2, lire en ligne), p. 73-104
• Jean-Éric Pin, « Automates finis », dans Jacky Akoka et Isabelle Comyn-Wattiau (éditeurs), Encyclopédie de l'informatique et des systèmes d'information, Paris, Vuibert, 2006, xxxv+1941 (ISBN 978-2-7117-4846-4), p. 966-976.
• James A. Storer, An Introduction to Data Structures and Algorithms, Springer Science & Business Media, 2012, 599 p. (ISBN 978-1-4612-0075-8 et 146120075X, présentation en ligne)
• Alfred Aho, Monica Lam, Ravi Sethi et Jeffrey Ullman (trad. de l'anglais par Philippe Deschamp, Bernard Lorho, Benoît Sagot et François Thomasset), Compilateurs : Principes, techniques et outils [« Compilers: Principles, Techniques, and Tools »], France, Pearson Education, novembre 2007, 2^e éd. (1^re éd. 1977), 901 p. (ISBN 978-2-7440-7037-2, présentation en ligne)

• « Z.100 : Langage de description et de spécification - Présentation générale de SDL-2010 », Union internationale des télécommunications, 1^er septembre 2015.
• Miro Samek, Practical Statecharts in C/C++ : Quantum Programming for Embedded Systems, CRC Press, 2002, 416 p. (ISBN 978-1-57820-110-5, lire en ligne).
• (en) Miro Samek, Practical UML Statecharts in C/C++ : Event-Driven Programming for Embedded Systems, Amsterdam, Newnes, 2009, 712 p. (ISBN 978-0-7506-8706-5, lire en ligne).
• Susan H. Rodger et Thomas W. Finley, JFLAP : An Interactive Formal Languages and Automata Package, Jones & Bartlett Learning, 2006, 192 p. (ISBN 978-0-7637-3834-1, présentation en ligne).
• Gérard Berry La vérification de modèles (model checking), Leçon du Collège de France du 25 mars 2015.

• Olivier Carton, Langages formels, calculabilité et complexité, 2008 [détail de l’édition] (lire en ligne)
• Sylvain Perifel, Complexité algorithmique, Ellipses, 2014, 432 p. (ISBN 9782729886929, lire en ligne) — (La version électronique est datée de juillet 2015.)
• Jacques Sakarovitch, Éléments de théorie des automates, Paris, Vuibert, 2003, 816 p. (ISBN 978-2-7117-4807-5, zbMATH 1188.68177)
• Gérard Berry, L’informatique du temps et des événements : Leçon inaugurale prononcée le jeudi 28 mars 2013, Collège de France, 2013, 88 p. (ISBN 978-2-7226-0277-9)
• James A. Anderson et Thomas J. Head, Automata Theory with Modern Applications, Cambridge University Press, 2006, 264 p. (ISBN 978-0-521-84887-9 et 0521848873).
• George S. Boolos, John P. Burgess et Richard C. Jeffrey, Computability and Logic, Cambridge, Cambridge University Press, 2007, 5^e éd. (1^re éd. 1989), 366 p. (ISBN 978-0-521-70146-4).
• Martin Davis, Ron Sigal et Elaine J. Weyuker, Computability, Complexity, and Languages : Fundamentals of Theoretical Computer Science, San Diego, Academic Press, 1994, 2^e éd., 609 p. (ISBN 978-0-12-206382-4, présentation en ligne).
• (en) John E. Hopcroft, Rajeev Motwani et Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2007, 3^e éd. (ISBN 978-0-32146225-1)
• Harry R. Lewis et Christos H. Papadimitriou, Elements of the Theory of Computation, Prentice Hall, 1998, 2^e éd., 361 p. (ISBN 978-0-13-262478-7).
• Peter Linz, An Introduction to Formal Languages and Automata, Sudbury, MA, Jones & Bartlett Publishers, 2011, 5^e éd., 437 p. (ISBN 978-1-4496-1552-9, présentation en ligne).
• Sanjeev Arora et Boaz Barak, Computational Complexity : A Modern Approach, Cambridge University Press, 2009, 579 p. (ISBN 978-0-521-42426-4, présentation en ligne).
• Nicholas Pippenger, Theories of Computability, Cambridge, Cambridge University Press, 2010, 264 p. (ISBN 978-0-521-15343-0)
• Michael Sipser, Introduction to the theory of computation, Boston, MA, Cengage Learning, 2013, 3^e éd., 480 p. (ISBN 978-1-133-18779-0, OCLC 761858892, présentation en ligne).

• Yuri Gurevich, « Sequential Abstract State Machines Capture Sequential Algorithms », ACM Transactions on Computational Logic, vol. 1, n^o 1,‎ juillet 2000, p. 77–111 (DOI 10.1145/343369.343384, lire en ligne)
• Sergey Goncharov, Stefan Milius et Alexandra Silva, « Toward a Uniform Theory of Effectful State Machines », ACM Transactions on Computational Logic, vol. 21, n^o 3,‎ 2020, article n^o 23 (63 p.) (ISSN 1529-3785, DOI 10.1145/3372880).

• Trevor Hastie, Robert Tibshirani et Jerome Friedman, The elements of statistical learning : data mining, inference, and prediction, New York, Springer, 2009, 2^e éd., xxii+745 (ISBN 978-0-387-84857-0)
• Vincent Barra, Antoine Cornuéjols, Laurent Miclet, Apprentissage Artificiel : Concepts et algorithmes, Eyrolles, 2021 (ISBN 978-2-416-001-04-8) [détail des éditions]
• (en) David MacKay, Information Theory, Inference, and Learning Algorithms, Cambridge University Press, 2003 (ISBN 0-521-64298-1) [détail des éditions]
• (en) Tom M. Mitchell, Machine Learning, 1997 [détail des éditions]
• (en) Christopher M. Bishop, Pattern Recognition And Machine Learning, Springer, 2006 (ISBN 0-387-31073-8) [détail des éditions]