1.3NFA → DFA: subset construction
The idea
The subset construction turns an NFA into a DFA whose states are sets of NFA states.
Think of it like this: Instead of cloning yourself, you keep a list of everywhere the clones are and update the whole list at once.
Why it exists
It proves NFA = DFA, and it is the standard exam procedure for counting DFA states.
How it works
- Start state = ε-closure of the NFA start state.
- For each symbol a: take every state in the current set, follow a-moves, then ε-closure.
- Repeat for each new set until no new set appears.
- A set is final if it contains an NFA final state. n states give at most 2ⁿ sets.
Worked example: Third symbol from the end is a
The NFA has 4 states but the reachable DFA has 8 = 2³ states: it must remember the last three symbols.
Now play with it
- →Press "Add next DFA state" and watch each new subset appear.
- →Compare the NFA size, reachable DFA size and the 2ⁿ bound.
| DFA state | = NFA states | on a | on b |
|---|---|---|---|
| A | {q0} | B | A |
| B | {q0,q1} | C | D |
| C | {q0,q1,q2} | E | F |
| D | {q0,q2} | G | H |
| *E | {q0,q1,q2,q3} | E | F |
| *F | {q0,q2,q3} | G | H |
| *G | {q0,q1,q3} | C | D |
| *H | {q0,q3} | B | A |
* = final DFA state (contains an NFA final state). Only reachable subsets are built, so the DFA is often smaller than 2ⁿ, but some languages really need it.
Check yourself
An NFA with 3 states is converted to a DFA by the subset construction. The maximum number of DFA states is
Exam notes (the dense version)
Each DFA state is a set of NFA states. Start from the ε-closure of the start state; for each symbol take move(set, a) and then its ε-closure; a DFA state is final if it contains an NFA final state. n NFA states can give up to 2n DFA states.
Previous year questions: Finite Automata (DFA, NFA, ε-NFA) (6)
PYQs are grouped by topic, so this is the full set for Finite Automata (DFA, NFA, ε-NFA); try the ones that match this subtopic. Open all 6 on the topic page.