Regex to DFA Converter (NFA, Subset Construction, Minimal DFA)
Convert a regular expression to a Thompson NFA, a DFA by subset construction and a minimal DFA, with transition tables and accept/reject tests on strings.
The alphabet is the set of symbols used in the expression: a, b.
Minimal DFA states are named after the DFA states they merge; "—" is a missing transition, i.e. the input is rejected.
| State | ε | a | b |
|---|---|---|---|
| → 0 | {1,2} | — | — |
| 1 | {3,4} | — | — |
| 2 | — | {5} | — |
| 3 | — | {6} | — |
| 4 | — | — | {7} |
| 5 | — | — | {8} |
| 6 | {9} | — | — |
| 7 | {9} | — | — |
| 8 | — | — | {10} |
| 9 | {1,2} | — | — |
| * 10 | — | — | — |
| State | NFA states | a | b |
|---|---|---|---|
| → A | {0,1,2,3,4} | B | C |
| B | {1,2,3,4,5,6,9} | B | D |
| C | {1,2,3,4,7,9} | B | C |
| D | {1,2,3,4,7,8,9} | B | E |
| * E | {1,2,3,4,7,9,10} | B | C |
| State | a | b |
|---|---|---|
| → AC | B | AC |
| B | B | D |
| D | B | E |
| * E | B | AC |
| String | Result | DFA path |
|---|---|---|
| abb | Accept | A → B → D → E |
| aabb | Accept | A → B → B → D → E |
| babb | Accept | A → C → B → D → E |
| ab | Reject | A → B → D |
| abba | Reject | A → B → D → E → B |
Compiler and automata courses turn regular expressions into machines in three steps: Thompson's construction gives an NFA with ε-moves, the subset construction turns it into a DFA, and minimization merges states that behave the same. This tool performs all three for a formal regular expression and prints the transition table of each machine, with start and accepting states marked, then runs your test strings through the minimal DFA and shows the path each one takes.
How to use this tool
- Type a regular expression with |, *, +, ?, parentheses and ε (or eps).
- Say whether + means "one or more" or "or" as in some textbooks.
- Enter strings to test, one per line (an empty line tests the empty string).
- Read the NFA, DFA and minimal DFA tables and the accept/reject results.
Formula
DFA state = ε-closure of a set of NFA states · move(T, a) = NFA states reachable from T on a · minimal DFA = classes of states with the same future behaviour
Thompson's construction gives every symbol two states and adds two states for each |, * , + or ?; concatenation merges the end of one part with the start of the next, as in the Dragon Book. The subset construction names DFA states A, B, C … in the order they are discovered. Minimization starts from the split accepting / non-accepting and refines it until states in a group go to the same groups on every symbol (Moore's algorithm, the same result as Hopcroft's). A dead state collects missing transitions; it can be shown or hidden.
Example
For (a|b)*abb, Thompson's construction gives 11 NFA states. The subset construction produces 5 DFA states, A to E, with exactly the transitions of the Dragon Book's table; E is the only accepting state. A and C behave identically, so the minimal DFA has 4 states: AC, B, D and E. Of the test strings, abb, aabb and babb are accepted; ab and abba are rejected.
Frequently asked questions
Why can the DFA have more states than the NFA?
Each DFA state stands for a set of NFA states, and there can be up to 2ⁿ such sets. Usually only a few are reachable, but some expressions really do need exponentially many — the tool stops at 2,000.
Is this the same as regex in programming languages?
No. This is the formal notation of automata theory: only union, concatenation, star, plus and optional. Features such as back-references or lookahead are not regular and cannot be turned into a DFA.
What is the dead state?
A non-accepting state that loops to itself on every symbol. It stands for "this input can never be accepted". Tables often leave it out; tick the option to show it.
Sources
Last updated:
Page address with these inputs: https://kakao.mobile/tools/regex-to-dfa-tool/
Cite or embed this tool
kakaoCalc. (2026, November 8). Regex to DFA Converter (NFA, Subset Construction, Minimal DFA). https://kakao.mobile/tools/regex-to-dfa-tool/
“Regex to DFA Converter (NFA, Subset Construction, Minimal DFA).” kakaoCalc, 8 Nov. 2026, kakao.mobile/tools/regex-to-dfa-tool/.
Paste this code into your page. The widget runs in your visitors' browsers, shows no ads and keeps a link back to this page. Embedding terms