Developer tool
Regex to NFA & DFA Converter
Convert a regular expression into an NFA, DFA, and minimized DFA using Thompson's construction, subset construction, and Hopcroft's algorithm. Everything runs locally.
Operators: concatenation ab, union a|b, star a*, plus a+, optional a?, groups (…). Escape a metacharacter with \.
About this tool
See the lexical analyzer pipeline, one stage at a time
A lexer generator turns a regular expression into a finite-state machine that a scanner can execute. This tool runs the three textbook stages in order: Thompson's construction expands the expression into a nondeterministic automaton with epsilon moves, subset (powerset) construction removes the nondeterminism by tracking sets of NFA states, and Hopcroft's algorithm collapses equivalent states into the provably smallest deterministic automaton for the same language.
Each stage draws the machine as a state diagram, with epsilon moves dashed so they read apart from symbol moves, alongside a labeled transition table, the start and accepting states, and how many states survived, so you can watch the machine shrink from NFA to DFA to minimal DFA. A built-in string tester runs any input on the minimized DFA and traces the exact state path, which is the same acceptance test a generated scanner would perform. Use it to check homework, study for an automata exam, or sanity-check a hand-drawn diagram.
How it works
Convert a regex in three steps
- 1Enter an expression
Type a regular expression using concatenation, |, *, +, ?, and parentheses, or load the sample.
- 2Compare the stages
Switch between the NFA, DFA, and minimized DFA to compare each state diagram, transition table, and state count.
- 3Test a string
Type an input string to see whether the minimized DFA accepts it and follow the state-by-state path.
Common questions
Regex to automata FAQ
Which regular expression syntax is supported?
The classic formal-language operators used in compiler courses: concatenation (ab), union (a|b), Kleene star (a*), one-or-more (a+), optional (a?), and grouping with parentheses. Escape a metacharacter with a backslash to match it literally, for example \* for a star. Character classes, anchors, and backreferences are not part of this theoretical model.
What is the difference between an NFA and a DFA here?
Thompson's construction produces a nondeterministic finite automaton (NFA) with epsilon (ε) transitions, so a state can have several moves on the same symbol. Subset construction then builds an equivalent deterministic finite automaton (DFA) where every state has at most one move per symbol, and Hopcroft's algorithm merges indistinguishable DFA states into the smallest equivalent DFA.
Why does the DFA sometimes have no transition for a symbol?
This tool shows a partial DFA: transitions that would lead to an empty (dead) set of states are omitted for clarity. During minimization those trap states are merged and dropped, so a string that runs off the end of the table is simply rejected.
Why can two states merge during minimization?
Two DFA states are equivalent when no string can tell them apart, meaning both accept exactly the same set of continuations. Hopcroft's algorithm repeatedly partitions the states, splitting a group whenever a symbol sends its members into different groups, until no group can be split further. Each surviving group becomes one state of the minimal DFA.
Is my expression uploaded anywhere?
No. Parsing, all three construction stages, and the string tester run entirely in your browser with JavaScript. Nothing you type is sent to a server.