Simulic
Français

Automates finis – feux tricolores, DFA, NFA et langages réguliers

InformatiqueAlgorithmique et résolution de problèmes15–16 ans

Chargement…

Utiliser avec ma classe ✨ Personnaliser avec l'IA Signaler un problème

Faites avancer pas à pas des automates d’exemple (feu tricolore, distributeur, tourniquet) sur une suite d’événements et observez l’état courant, la sortie et une table de trace ; ajoutez, déplacez et reliez des états pour dessiner votre propre automate. Le mode Accepteur teste les mots qu’accepte un DFA ou un NFA (nombres binaires divisibles par 3, mots se terminant par ab), avec la table de transition, une expression régulière et une grammaire régulière équivalentes, et la conversion d’un NFA en DFA. Une note compare chaque modèle au système réel pour aborder l’abstraction.

Leçon : Automates finis : états, transitions et sorties ; automates finis déterministes et non déterministes ; expressions régulières et grammaires régulières

Ce qu’elle montre

Un automate fini possède un ensemble fini d’états, un état initial, un alphabet d’entrée et des transitions de la forme état + symbole → état suivant. Il ne mémorise rien d’autre que son état courant. Une machine de Mealy produit des sorties sur ses transitions, une machine de Moore associe les sorties à ses états, et un accepteur répond par oui ou par non : un mot appartient-il à un langage ? Les langages acceptés par les automates finis sont exactement les langages réguliers, que décrivent aussi les expressions régulières et les grammaires régulières. Tout NFA (AFN) peut être transformé en un DFA (AFD) équivalent par la construction des sous-ensembles.

Mode d’emploi

En mode Machine avec sortie, choisissez une Machine d’exemple et cliquez sur Pas ou Lecture pour fournir un à un les symboles du ruban ; les boutons de symbole envoient des événements supplémentaires. En mode Accepteur, choisissez un Automate d’exemple, saisissez un Mot à lire et parcourez-le pas à pas, puis utilisez Tester ou Lister les mots acceptés. Ouvrez Modifier la machine pour ajouter, déplacer et relier des états, ou cliquez sur Convertir le NFA en DFA.

Paramètres modifiables

  • Mode Machine avec sortie, Accepteur
  • Machine d’exemple (mode Machine avec sortie) Feu tricolore, Distributeur, Tourniquet
  • Automate d’exemple (mode Accepteur) DFA : nombres binaires divisibles par 3, NFA : mots se terminant par ab, DFA : mots se terminant par ab, DFA : nombre pair de 1 (bit de parité)
  • Mot à lire (vide = mot d’exemple)
  • Vitesse d’exécution 0,5–4 symboles/s
  • Ouvrir le panneau Modifier la machine

Questions à explorer

  1. Quels détails d’un vrai feu tricolore le modèle laisse-t-il de côté, et pourquoi est-ce acceptable ?
  2. En le suivant état par état, le mot 110 est-il accepté par l’automate de divisibilité par 3 ?
  3. Pourquoi le NFA des mots se terminant par ab nécessite-t-il moins de transitions que le DFA équivalent ?

Simulations associées