Animateur d'automate fini

Un automate fini dispose d'une mémoire fixe — son ensemble d'états. Quelle que soit la longueur de la chaîne d'entrée, la machine n'utilise jamais plus de mémoire que son nombre d'états. C'est pourquoi les AFD ne peuvent pas compter sans limite : aucun état ne peut « se souvenir » d'un entier arbitraire. Le lemme de l'étoile précise cela : toute chaîne suffisamment longue acceptée par un AFD peut voir une section médiane répétée un nombre arbitraire de fois tout en restant acceptée. Les langages qui ne peuvent pas être pompés (comme aⁿbⁿ, nombre égal de a et de b) nécessitent un automate à pile ou une machine de Turing. Le théorème de Myhill-Nerode donne le minimum exact : le nombre d'états est égal au nombre de classes d'équivalence distinguables des préfixes d'entrée.

Un automate fini déterministe n'est qu'un diagramme étiqueté d'états reliés par des flèches. Pour chaque état et chaque symbole d'entrée, il existe exactement une flèche à suivre : il n'y a donc jamais de choix. La machine lit la chaîne une seule fois, de gauche à droite, et se retrouve dans un unique état. Si cet état final est marqué comme acceptant, l'entrée appartient au langage. Il suffit de faire glisser un jeton le long des flèches — c'est précisément ce que montre cet outil.

Les automates finis ne sont pas nés en informatique. En 1943, Warren McCulloch et Walter Pitts décrivirent les neurones comme de simples unités marche/arrêt reliées entre elles, ce qui devint le premier modèle mathématique d'une machine à états finis. En 1951, Stephen Kleene analysa quels motifs de tels 'réseaux de neurones' pouvaient reconnaître et les nomma événements réguliers — l'origine des expressions régulières actuelles. L'automate que vous parcourez ici descend donc directement d'une tentative d'expliquer comment le cerveau calcule.