ChatDiagram
Essayer gratuitement
4 templates · State diagram

Thompson Construction Epsilon-NFA State Diagrams

Thompson's construction is a systematic method for converting a regular expression into an epsilon-NFA (ε-NFA). This page collects examples of epsilon-NFAs built using Thompson construction for various regex patterns, from simple tokens to complex expressions. Use these diagrams as a visual reference when studying automata theory, designing lexical analyzers, or verifying your own constructions.

Standard OMG UML 2.5.1 §14 + Harel (1987) statechartEngine schematex-stateExport SVG · PNG · PDF
4 modèles
Diagramme d’états Thompson Construction Epsilon-NFA
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. 01Enter your regular expression

    Type or paste the regex you want to convert, using standard syntax like a|b, a*, (ab), etc.

  2. 02Apply Thompson's construction

    The tool automatically applies the construction rules to build the epsilon-NFA, creating states and transitions for each subexpression.

  3. 03Review the generated diagram

    Inspect the state diagram to verify that it correctly represents your regex, including all epsilon transitions.

  4. 04Adjust layout and labels

    Drag states, reroute transitions, or edit labels to improve readability without changing the automaton's behavior.

  5. 05Export or share your ε-NFA

    Download the diagram as an image or PDF, or share a live link for collaboration.

FAQ

Questions about state diagram templates

What is Thompson's construction?

Thompson's construction is an algorithm that converts a regular expression into an equivalent epsilon-NFA. It works by recursively breaking the regex into atomic subexpressions and combining them using rules for concatenation, union, and Kleene star.

Why does Thompson's construction use epsilon transitions?

Epsilon transitions allow the construction to combine smaller automata without needing to merge states or create complex transitions. They act as 'glue' to connect the sub-automata while preserving the overall language.

Can I convert any regular expression to an epsilon-NFA with this tool?

Yes, as long as the regex uses standard operators (union, concatenation, star, plus, optional, character classes). The tool supports the full syntax and generates the corresponding epsilon-NFA automatically.

How is Thompson's construction different from other regex-to-NFA methods?

Thompson's construction is simple and systematic, producing an NFA with a number of states at most twice the length of the regex. Other methods like Glushkov's construction can produce fewer states but are more complex to implement.

Can I export the epsilon-NFA diagram for use in documents?

Absolutely. The tool allows you to export the diagram as PNG, SVG, or PDF, so you can include it in reports, assignments, or presentations.