ChatDiagram
Essayer gratuitement
4 templates · State diagram

Diagrammes d’états ε-NFA avec la construction de Thompson

La construction de Thompson est une méthode systématique permettant de convertir une expression régulière en ε-NFA. Cette page rassemble des exemples d’ε-NFA construits avec la méthode de Thompson pour différents motifs d’expressions régulières, des jetons simples aux expressions complexes. Utilisez ces diagrammes comme référence visuelle pour étudier la théorie des automates, concevoir des analyseurs lexicaux ou vérifier vos propres constructions.

Standard OMG UML 2.5.1 §14 + Harel (1987) statechartEngine schematex-stateExport SVG · PNG · PDF
4 modèles
Diagramme d’états Diagrammes d’états ε-NFA avec la construction de Thompson
Thompson ε-NFA for Regex [0-9]+Thompson ε-NFA for Regex [0-9]+Diagramme d’étatsUtiliser le modèle →Thompson ε-NFA for Identifier RegexThompson ε-NFA for Identifier RegexDiagramme d’étatsUtiliser le modèle →Thompson Construction ε-NFA for (a|b)*abbThompson Construction ε-NFA for (a|b)*abbDiagramme d’étatsUtiliser le modèle →ε-NFA for (0|1)*101 using Thompson Constructionε-NFA for (0|1)*101 using Thompson ConstructionDiagramme d’étatsUtiliser le modèle →

Nothing close enough? Start from a blank state diagram → Describe it in one paragraph.

How to

How to use a state diagram template.

  1. 01Saisir votre expression régulière

    Saisissez ou collez l’expression régulière à convertir en utilisant une syntaxe standard comme a|b, a*, (ab), etc.

  2. 02Appliquer la construction de Thompson

    L’outil applique automatiquement les règles de construction pour créer l’ε-NFA, avec des états et des transitions pour chaque sous-expression.

  3. 03Vérifier le diagramme généré

    Examinez le diagramme d’états pour vérifier qu’il représente correctement votre expression régulière, y compris toutes les transitions epsilon.

  4. 04Ajuster la disposition et les libellés

    Déplacez les états, redirigez les transitions ou modifiez les libellés pour améliorer la lisibilité sans changer le comportement de l’automate.

  5. 05Exporter ou partager votre ε-NFA

    Téléchargez le diagramme sous forme d’image ou de PDF, ou partagez un lien actif pour collaborer.

FAQ

Questions about state diagram templates

Qu’est-ce que la construction de Thompson ?

La construction de Thompson est un algorithme qui convertit une expression régulière en un ε-NFA équivalent. Elle décompose récursivement l’expression régulière en sous-expressions atomiques, puis les combine à l’aide de règles de concaténation, d’union et d’étoile de Kleene.

Pourquoi la construction de Thompson utilise-t-elle des transitions epsilon ?

Les transitions epsilon permettent à la construction de combiner de petits automates sans fusionner leurs états ni créer de transitions complexes. Elles servent de « colle » pour relier les sous-automates tout en préservant le langage global.

Puis-je convertir n’importe quelle expression régulière en ε-NFA avec cet outil ?

Oui, à condition que l’expression régulière utilise les opérateurs standard (union, concaténation, étoile, plus, optionnel, classes de caractères). L’outil prend en charge toute cette syntaxe et génère automatiquement l’ε-NFA correspondant.

En quoi la construction de Thompson diffère-t-elle des autres méthodes de conversion d’expressions régulières en NFA ?

La construction de Thompson est simple et systématique : elle produit un NFA comportant au plus deux fois la longueur de l’expression régulière en nombre d’états. D’autres méthodes, comme la construction de Glushkov, peuvent produire moins d’états, mais elles sont plus complexes à implémenter.

Puis-je exporter le diagramme ε-NFA pour l’utiliser dans des documents ?

Absolument. L’outil vous permet d’exporter le diagramme au format PNG, SVG ou PDF afin de l’inclure dans des rapports, devoirs ou présentations.