Exemples de diagrammes NFA.
Un seul outil, quatre demandes. Tous les schémas ci-dessous sont de vrais rendus.
Qu'est-ce qu'un diagramme NFA ?
Un diagramme NFA est un diagramme d'états représentant un automate fini non déterministe. Les cercles sont les états, les flèches sont les transitions, une flèche entrante indique l'état initial et un double cercle indique un état accepteur.
Contrairement à un DFA, un NFA peut effectuer plusieurs transitions avec le même symbole d'entrée et utiliser des transitions epsilon qui ne consomment aucune entrée. Une chaîne est acceptée lorsqu'au moins un chemin se termine dans un état accepteur.
- Standard
- OMG UML 2.5.1 §14 + Harel (1987) statechart
- Engine
- schematex-state
- Editable
- Double-click text, drag nodes
- Export
- SVG · PNG · PDF
Qui utilise les diagrammes NFA.
Exercices sur les langages réguliers montrant comment une machine reconnaît un suffixe, un préfixe ou une sous-chaîne.
Petites constructions de NFA-ε qui rendent visible en cours l'union d'expressions régulières.
Préfixes de jetons alternatifs représentés sous forme de branches avant leur conversion en implémentation.
Comment créer un diagramme NFA en trois étapes.
Décrivez votre idée
Un paragraphe suffit pour commencer.
Découvrez le schéma
Généré avec le moteur adapté.
Indiquez les modifications
Chaque modification crée une nouvelle version.
Questions fréquentes
Qu'est-ce qu'un NFA ?
Un automate fini non déterministe est une machine à états finis qui peut avoir plusieurs transitions possibles pour un même symbole d'entrée. Il accepte lorsqu'au moins un chemin dans la machine se termine dans un état accepteur.
Quelle est la différence entre un NFA et un DFA ?
Un DFA possède un unique état suivant pour chaque état et chaque symbole d'entrée. Un NFA peut se ramifier vers plusieurs états et inclure des transitions epsilon, mais les NFA et les DFA reconnaissent la même classe de langages réguliers.
Qu'est-ce qu'une transition epsilon ?
Une transition epsilon change d'état sans consommer de caractère de l'entrée. Elle sert couramment à réunir ou séparer des branches lors de la construction d'un NFA à partir d'une expression régulière.
Comment les états accepteurs sont-ils représentés ?
Un état accepteur, ou final, est représenté par un double cercle. La machine accepte uniquement si un chemin se termine dans cet état après la lecture de toute l'entrée.
Puis-je créer un NFA à partir d'une expression régulière ?
Oui. Décrivez l'expression et son alphabet, puis indiquez les groupements ou alternances que vous souhaitez rendre explicites dans le diagramme d'états.
D’autres schémas pour le même projet.
Créez votre premier NFA maintenant.
Compte gratuit, sans carte bancaire. Décrivez le langage et obtenez le diagramme d'états en moins d'une minute.
Ouvrir l’éditeur