Un automate fini est l’un des modèles de calcul les plus simples que l’on puisse imaginer, conçu pour reconnaître des motifs dans une suite de symboles lue de gauche à droite. On peut se le représenter comme un petit dispositif doté d’un nombre limité d’états, dont un état de départ et un ou plusieurs états considérés comme favorables. L’automate lit les symboles un à un, sans jamais revenir en arrière, et à chaque symbole lu il passe d’un état à un autre selon des règles fixées d’avance. Lorsque toute la suite a été lue, on regarde dans quel état l’automate se trouve: s’il s’agit d’un état favorable, la suite est acceptée, sinon elle est rejetée. Sa caractéristique essentielle, et sa limite, est de ne disposer d’aucune mémoire au-delà de son état courant: il ne peut retenir qu’une quantité finie et bornée d’informations sur ce qu’il a déjà lu.
La théorie des automates finis s’est constituée dans les années 1940 et 1950, à la croisée de plusieurs préoccupations. Les premiers modèles furent proposés par McCulloch et Pitts pour représenter de façon idéalisée le fonctionnement des neurones, puis Kleene, Rabin et Scott en firent une théorie mathématique aboutie. On découvrit que les automates finis correspondent exactement à une famille de motifs appelés langages réguliers, que l’on peut aussi décrire par des expressions dites régulières. Cette double description, par machine ou par formule, révéla une correspondance profonde et féconde entre une notion mécanique et une notion purement symbolique, l’une des premières réussites de l’informatique théorique naissante.
Malgré leur simplicité, les automates finis sont extraordinairement utiles en pratique et se cachent dans quantité d’outils quotidiens. Les expressions régulières, employées partout pour rechercher ou valider du texte, comme une adresse électronique ou un numéro bien formé, reposent directement sur eux. Les compilateurs s’en servent pour découper un code source en mots élémentaires, et on les retrouve dans les protocoles de communication, dans la conception de circuits électroniques et dans le contrôle de nombreux appareils dont le comportement se décrit par un petit nombre d’états et de transitions, d’un distributeur automatique à un feu de circulation. Leur simplicité même explique leur efficacité: parce qu’ils ne mémorisent presque rien, ils sont rapides, économes et faciles à analyser.
Laisser un commentaire