Animateur d'automate fini

parcourez les transitions d'un AFD sur un diagramme d'états en direct

Exemple résolu — Animateur d'automate fini

Symbole suivant	'1'

Ce sont les valeurs affichées par le calculateur à l’ouverture de la page. Modifiez une entrée ci-dessus pour les recalculer.

Chargement de la simulation interactive...

mémoire finie, chaînes infinies 🖖

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 jeton, un chemin 🖖

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.

né d'un modèle de neurones 🖖

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.

Problème entièrement résolu

Pourquoi aucune machine finie ne peut apparier les 0 et les 1, quel que soit le nombre d'états qu'on lui donne 8 étapes
L'automate de parité présent sur cette page possède deux états, et il lit 101101, six symboles, sans jamais avoir besoin d'un troisième. Donnez-lui six millions de symboles, et il n'en demande toujours que deux. Que ne peut donc pas faire une machine ayant un nombre fixe d'états ? Et comment prouver qu'une machine n'existe pas, au lieu d'échouer simplement à en trouver une ?
1. Observez la machine dont vous disposez. L'automate de parité démarre dans e, et chaque 1 le fait basculer. Six symboles plus tard, il est de retour dans e et l'entrée est acceptée. Rien ne s'est accumulé en chemin : au sixième symbole, la machine est exactement dans le même état qu'elle aurait pu l'être au premier symbole.
  
  $e 1 o 0 o 1 e 1 o 0 o 1 e$
2. Voilà toute la ressource disponible. La mémoire d'un automate fini déterministe réside dans l'état où il se trouve et rien d'autre. Aucun compteur, aucune pile, aucun ruban sur lequel écrire. Après avoir lu un préfixe quelconque, tout ce que la machine sait de ce préfixe est lequel de ses k états elle occupe désormais.
  
  $∣ Q ∣ = k ⟹ at most k distinguishable pasts$
3. Trouvez donc une tâche qui nécessite visiblement davantage. Prenez les chaînes formées d'un certain nombre de zéros suivis d'exactement autant de uns. 01 en fait partie, 0011 aussi, mais pas 001, ni 0110.
  
  $L = {0^{n} 1^{n} : n \geq 0}$
4. Supposez qu'un automate fini déterministe à k états le reconnaisse. Ne demandez pas à quoi ressemble la machine — on ne vous le dira jamais. Donnez-lui simplement les k+1 préfixes composés de 0 à k zéros, et notez dans quel état chacun d'eux la laisse.
  
  $0^{0}, 0^{1}, \dots, 0^{k} ⟶ k + 1 strings into k states$
5. Principe des tiroirs. Il y a plus de préfixes que d'états, donc deux d'entre eux aboutissent au même endroit. Appelons-les 0ⁱ et 0ʲ avec i inférieur à j. À partir de cet instant, la machine ne peut plus les distinguer, et non pas parce qu'elle serait mal conçue. L'état est tout ce dont elle dispose, et les deux chaînes l'ont amenée dans le même.
  
  $δ^{*} (q_{0}, 0^{i}) = δ^{*} (q_{0}, 0^{j}), i < j \leq k$
6. Fournissez maintenant la même suite aux deux chaînes : i uns. Même état de départ, mêmes symboles, donc même état d'arrivée, et par conséquent même verdict. La machine n'a aucune marge de manœuvre pour faire autrement.
  
  $δ^{*} (q_{0}, 0^{i} 1^{i}) = δ^{*} (q_{0}, 0^{j} 1^{i})$
7. Or, les deux verdicts doivent différer. 0ⁱ1ⁱ possède des nombres d'occurrences identiques et fait partie du langage ; 0ʲ1ⁱ n'en fait pas partie, car j n'est pas égal à i. L'une des chaînes doit être acceptée et l'autre refusée, pourtant la machine leur donne la même réponse. C'est l'hypothèse de son existence qui s'effondre.
  
  $0^{i} 1^{i} \in L, 0^{j} 1^{i} \in / L$
8. Relisez l'argumentation et remarquez ce qui n'y figure jamais : une valeur particulière de k. Deux (la taille de l'automate de parité) ou deux milliards : dans tous les cas, k+1 préfixes sont plus nombreux que k états. Fixez toutefois un plafond à n, et le langage devient immédiatement reconnaissable par un automate fini : apparier jusqu'à N nécessite 2N+2 états, soit 22 pour N = 10 et 202 pour N = 100.
  
  ${0^{n} 1^{n} : n \leq N} needs 2 N + 2 states$
Réponse

Aucun automate fini ne le reconnaît, quelle que soit sa taille. La preuve ne nécessite aucun détail sur la façon dont la machine est construite, seulement le fait que k+1 éléments ne peuvent occuper k emplacements sans que deux d'entre eux n'en partagent un, et que partager un état équivaut à oublier. L'automate de parité montre la même chose en miniature : donnez-lui 0, puis 00, puis 000, et tous trois le laissent dans e, car il ne prend aucunement en compte les zéros.

Toute la difficulté réside dans ce plafond. Apparier jusqu'à N est facile et nécessite 2N+2 états, soit une paire supplémentaire pour chaque symbole qu'on souhaite atteindre, et ce nombre grandit sans s'arrêter : ainsi, chaque N particulier possède son automate, mais aucun automate ne convient pour tout N. Cet écart est la définition même de la « mémoire finie », et c'est pourquoi l'étape suivante après un automate fini déterministe est définie en lui ajoutant une pile : une mémoire non bornée, réintroduite précisément parce que son absence a un coût.

Références (2)

Insight block 3 — the nerve-net model the finite automaton descends from: W. S. McCulloch and W. Pitts, "A logical calculus of the ideas immanent in nervous activity." Bulletin of Mathematical Biophysics 5(4), 115–133, 1943.
Insight block 1 — the theorem that fixes the minimum state count: A. Nerode, "Linear automaton transformations." Proceedings of the American Mathematical Society 9(4), 541–544, 1958.

Par l’équipe 42Math · Mis à jour 2026-06-03

Vérifié sur des sources publiées. Corrections bienvenues. Politique éditoriale · Corrections

Toutes les leçons : Informatique →

Exemples de problèmes

se termine par 01 - Le reconnaisseur de suffixe accepte les chaînes se terminant par 01.
rejetée (se termine par 10) - Avancez jusqu'à la fin : la machine s'arrête en q1 et rejette, bien qu'elle ait séjourné dans l'état d'acceptation q2 à mi-parcours. Lire un 01 quelque part au milieu n'est pas équivalent à terminer par cette séquence. La réponse complète d'un AFD réside dans l'état atteint après le tout dernier symbole. L'automate ne dispose d'aucun moyen de se souvenir qu'il a déjà connu une meilleure situation.
nombre pair de 1 ✓ - L'automate de parité accepte les chaînes binaires ayant un nombre pair de 1.
nombre impair de 1 ✗ - Trois 1 en entrée, et la machine de parité bascule pour chacun d'eux : e, o, o, e, o. Elle termine en o et rejette. Absolument rien n'est compté ici. Ses deux états représentent tout ce qu'elle possède et l'intégralité de ce dont elle a besoin. Savoir si le compte en cours est impair constitue en effet la seule information digne d'être mémorisée pour une chaîne, quelle que soit sa longueur.
contient 101 ✓ - La machine atteint s3 au quatrième symbole et ne peut plus s'en échapper : s3 boucle sur s3 avec un 0 comme avec un 1. Trois autres symboles défilent, le verdict étant déjà scellé pour chacun d'eux. L'état puits est le mécanisme par lequel un AFD s'engage sur un oui avant l'épuisement de l'entrée, sans rien conserver du moment où l'événement s'est produit.
pas de 101 ✗ - Rejeté en s2, que la légende désigne par « 10 lu — à un symbole du but ». Un 1 de plus à la fin aurait achevé le motif et bloqué la machine dans s3 pour de bon. L'état dans lequel vous atterrissez indique à quel point vous étiez proche, une nuance que le simple fait d'accepter ou de rejeter ne révélera jamais par lui-même.