Converting a regular expression to a minimal DFA is a pipeline, not a single construction. Thompson's method builds an epsilon-NFA. Subset construction turns reachable sets of NFA states into deterministic states. Minimisation then merges deterministic states with the same future behaviour.
This example uses **(a|b)*a(a|b)**. It describes words over {a, b} whose penultimate symbol is a. A word must have enough symbols for that final pair; the empty word and a single symbol are rejected. Every state, transition, partition and acceptance result below was generated by the site's automata libraries.
Read the regular expression first
The prefix (a|b)* can consume any sequence of a and b symbols, including no symbols. The next a fixes the first symbol of the final pair. The last (a|b) consumes its final symbol. The bar means union, adjacent expressions mean concatenation, and the star means zero or more repetitions.
These are textbook regular-expression operators, not JavaScript anchors, lookarounds or backreferences. Start with the regex-to-NFA converter to inspect the generated machine. State names are construction bookkeeping: another correct Thompson implementation may use different names or introduce extra epsilon states while recognising the same language.
Thompson construction: keep the epsilon edges
The generated NFA has 14 states. Its full transition table is below. A dash means no transition. Multiple destinations in one cell are nondeterministic choices, not a sequence of moves. Only epsilon transitions consume no input.
| NFA state | On ε | On a | On b |
|---|---|---|---|
| q0 (start) | q1, q2 | — | — |
| q1 | q3, q4 | — | — |
| q2 | — | q5 | — |
| q3 | — | q6 | — |
| q4 | — | — | q7 |
| q5 | q8, q9 | — | — |
| q6 | q10 | — | — |
| q7 | q10 | — | — |
| q8 | — | q11 | — |
| q9 | — | — | q12 |
| q10 | q2, q1 | — | — |
| q11 | q13 | — | — |
| q12 | q13 | — | — |
| q13 (accept) | — | — | — |
A symbol fragment consumes its symbol. A union adds epsilon choices, a concatenation joins fragments in sequence, and a star adds both a bypass and a way to repeat. This library merges a preceding fragment's accepting endpoint with the next fragment's starting endpoint during concatenation; the table above is the resulting construction, not an assumed textbook numbering.
Do not erase epsilon edges when converting to a DFA. They determine which states are active before the first input symbol and after every symbol-consuming move.
Subset construction: closure, move, closure
The initial deterministic state is the epsilon closure of the NFA start. For each reachable subset and each input symbol, collect all matching destinations, then take their epsilon closure. Discover a new DFA row whenever that resulting set has not been seen before.
A DFA subset is accepting if it contains any accepting NFA state. It does not need to consist entirely of accepting states. The subset converter reports empty targets as ∅ but normally omits a separate trap row. In this example every listed input transition leads to a nonempty reachable subset.
| DFA state | NFA-state subset | On a | On b |
|---|---|---|---|
| D0 (start) | {q0,q1,q2,q3,q4} | D1 | D2 |
| D1 | {q1,q2,q3,q4,q5,q6,q8,q9,q10} | D3 | D4 |
| D2 | {q1,q2,q3,q4,q7,q10} | D1 | D2 |
| D3 (accept) | {q1,q2,q3,q4,q5,q6,q8,q9,q10,q11,q13} | D3 | D4 |
| D4 (accept) | {q1,q2,q3,q4,q7,q10,q12,q13} | D1 | D2 |
Only 5 subsets are reachable from the start in this construction. The theoretical powerset includes unreachable combinations; there is no reason to build rows for all of them. Keep a consistent mapping from subset sets to the short D names so two differently ordered displays of the same set do not become two states.
The NFA-to-DFA converter performs this reachable-subset calculation. For character-class expressions, use the converter's class-aware alphabet handling rather than treating a printed class label as a single ordinary character; this example deliberately uses only the literal symbols a and b.
Minimise the deterministic machine
First remove unreachable states. Here the subset construction already discovered only reachable rows. Next split states into accepting and nonaccepting groups. Refine each group when two states transition, on the same symbol, into different current groups.
The library reports these partition rounds:
| Round | Partition |
|---|---|
| 0 | {D3, D4} ; {D0, D1, D2} |
| 1 | {D3} ; {D4} ; {D0, D2} ; {D1} |
Stop when refinement makes no further split. States remaining in one group cannot be distinguished by any future input word. The table-filling method reaches the same equivalence classes; its pair results are:
| Pair | First marked round | Distinguishing input symbol |
|---|---|---|
| D0, D1 | 1 | a |
| D0, D2 | unmarked (equivalent) | — |
| D1, D2 | 1 | a |
| D0, D3 | 0 | — |
| D1, D3 | 0 | — |
| D2, D3 | 0 | — |
| D0, D4 | 0 | — |
| D1, D4 | 0 | — |
| D2, D4 | 0 | — |
| D3, D4 | 1 | a |
An initial mark separates an accepting state from a nonaccepting state. Later marks come from transitions into an already distinguishable pair. Unmarked pairs are candidates for merging only after the procedure reaches its fixed point.
The minimal transition table
The result has 4 states. Each final state name below represents the corresponding equivalence class of the original deterministic states.
| State | On a | On b | Accepting? |
|---|---|---|---|
| D3 | D3 | D4 | yes |
| D4 | D1 | D0,D2 | yes |
| D0,D2 (start) | D1 | D0,D2 | no |
| D1 | D3 | D4 | no |
Use the DFA minimiser to compare partition refinement with pair marking. Accepting states remain accepting after merging; merging an accepting state with a nonaccepting one would immediately change whether the empty remaining suffix is accepted.
The minimal machine is unique up to state renaming for a fixed complete deterministic language model. Its printed state labels and drawing positions are not unique. A partial-DFA display may hide a rejecting trap state, so compare transition conventions before comparing raw state counts between tools.
Check the whole pipeline
The generated sample results agree across the NFA, subset DFA and minimal DFA:
| Word | NFA | DFA | Minimal DFA |
|---|---|---|---|
| ε | reject | reject | reject |
| a | reject | reject | reject |
| b | reject | reject | reject |
| aa | accept | accept | accept |
| ab | accept | accept | accept |
| ba | reject | reject | reject |
| bb | reject | reject | reject |
| aab | accept | accept | accept |
| aba | reject | reject | reject |
| abb | reject | reject | reject |
| baba | reject | reject | reject |
The construction script also compared the NFA and minimal DFA on every binary word through its short-word test bound. Such enumeration is a useful regression check; the reason the pipeline preserves the language is the construction and equivalence algorithms, not a finite sample alone.
Mistakes that change the answer
Forgetting the initial epsilon closure can lose valid paths before any input is read. Skipping closure after a symbol-consuming move can lose paths later. Marking a subset accepting only when all its members accept reverses the NFA's existential acceptance rule.
During minimisation, compare transition destinations by their current partition groups, not merely by whether the destination names happen to match. Different destination states can already be equivalent. Conversely, two states with the same accepting status may need to split because a later suffix distinguishes them.
Finally, keep the language description beside the tables. For this regex the penultimate-symbol condition gives an independent way to reason about the sample words and catch a misplaced accepting marker before it propagates through the next stage.
For a related walkthrough, read Thompson's Construction: Regex to NFA to DFA.