Uses Thompson's construction algorithm to convert regular expressions into NFAs (Nondeterministic Finite Automata) and renders state transition diagrams on Canvas. Helps understand the underlying principles of regex — a visualization tool for compiler theory and formal language study.
• Thompson's Construction: Systematic regex-to-NFA conversion
• Canvas Visualization: Draws state nodes and transition edges
• ε-Transition Labels: Clearly shows empty transitions
• State Statistics: Displays state count and transition count
• Export PNG: Save state diagrams as images
Step 1: Enter a regular expression. Supports a|b (alternation), ab (concatenation), a* (closure), a+ (positive closure), a? (optional), () (grouping), . (any character).
Step 2: Click "Generate NFA" — the Canvas automatically draws the state diagram. Single circles are normal states, double circles are accept states, and an arrow points to the start state.
Step 3: Review ε-transitions and character transitions. Click "Download PNG" to save the diagram for study notes or documentation.
Compiler Theory Study: Visualize the regex-to-automaton conversion process, intuitively understanding each step of Thompson's construction — a supplementary tool for formal language and automata theory courses.
Regex Engine Development: When building a custom regex engine, use NFA visualization to verify the construction algorithm's correctness and quickly identify bugs.
Technical Interview Prep: Regex-to-automaton conversion is a common interview topic. Use this tool to practice and verify hand-drawn NFAs.
Thompson's Construction Rules: ① Single char a: two states connected by an a-edge; ② Concatenation RS: R's accept state connects via ε to S's start; ③ Alternation R|S: new start connects via ε to R and S starts, R and S accepts connect via ε to new accept; ④ Closure R*: new start connects via ε to R's start and new accept, R's accept connects via ε back to R's start and to new accept.
NFA→DFA→Minimized DFA: The complete regex processing pipeline: Regex→NFA (Thompson)→DFA (Subset Construction)→Minimized DFA (Hopcroft). This tool implements the first step; subsequent steps can be done with other tools.
NFA (Nondeterministic Finite Automaton) is a computational model where each state can transition to multiple states on the same input symbol, and can make ε-transitions (move without consuming input). NFAs are equivalent representations of regular expressions.
Thompson's construction, invented by Ken Thompson, systematically converts regular expressions to NFAs. It recursively combines basic elements into complex structures, where each sub-NFA has exactly one start and one accept state.
Supports basic operators: concatenation (ab), alternation (a|b), closure (a*), positive closure (a+), optional (a?), grouping (()), character ranges ([a-z]), and any character (.). Backreferences and lookahead are not supported.
ε (epsilon) represents an empty transition — moving from one state to another without consuming any input character. ε-transitions are the core mechanism of Thompson's construction, used to connect sub-NFAs.
Single circles are normal states. Double circles are accept states (final states). The start state is indicated by an incoming arrow. A match succeeds when all input is consumed and the NFA is in an accept state.
The Subset Construction algorithm converts NFA to DFA. Each DFA state corresponds to a set of NFA states (ε-closure). While DFA states may grow exponentially, DFA matching is more efficient as it requires no backtracking.