Drawtomata / NFA to DFA converter
NFA to DFA converter
Draw or load an NFA above and press NFA → DFA. Drawtomata builds the DFA by subset construction and shows the full table of subsets, the resulting DFA and its transition table, then checks that both machines accept the same language.
How the subset construction works
Each state of the DFA stands for a set of NFA states: the states the NFA could be in after reading the same input.
- The start state of the DFA is {q0}, or the λ-closure of q0 if the NFA has λ-moves.
- For a DFA state S and a symbol a, the next state is the set of NFA states reachable from any state in S on a (followed by λ-moves, if any).
- Every new set becomes a new DFA state. Repeat until no new sets appear.
- A DFA state is final if its set contains at least one final state of the NFA. The empty set ∅ is the trap state.
Example
Pick NFA: ends with ab from the Examples menu above. It accepts strings over {a, b} that end in ab: q0 loops on a and b, q0 –a→ q1 and q1 –b→ q2, with q2 final.
| DFA state | a | b |
|---|---|---|
| → {q0} | {q0, q1} | {q0} |
| {q0, q1} | {q0, q1} | {q0, q2} |
| * {q0, q2} | {q0, q1} | {q0} |
Only three of the 2³ = 8 possible subsets are reachable, so the DFA has three states. The tool lists the subsets in the order they are discovered, which is how the table is written in an exam.
Questions
Can the DFA have more states than the NFA?
Yes. An NFA with n states can need up to 2ⁿ DFA states. The NFA for “the k-th symbol from the right is a” is the classic case where all 2ᵏ subsets are needed.
What if my NFA has λ (ε) moves?
Use the same button. The start state and every move are closed under λ-moves, and the λ-closure of each state is shown. To remove λ-moves first and keep an NFA, see ε-NFA to NFA.
Is the result minimal?
Not always. Run DFA minimization on it next to merge equivalent states.