The phrase “up to 2^n states” makes NFA-to-DFA conversion sound larger than it usually is. Most questions want the subsets that are actually reachable from the start, not every subset that could be written down. Once each DFA state is treated as a set of NFA states, the conversion is a fixed table-building procedure.
The subset-construction procedure
Subset construction simulates all NFA choices at once. Follow these rules in order:
A single DFA state represents a set of NFA states.
The DFA start state is the epsilon-closure of the NFA start state.
For a DFA subset S and input symbol x, take every x-transition from every NFA state in S, form their union, and then take the epsilon-closure of that union.
A DFA subset is accepting if it contains at least one accepting NFA state.
Continue only with new subsets reached from the table. Do not draw all 2^n subsets in advance.
If a reachable state has no destination for some input, use the empty subset as an explicit dead state. A DFA transition function must be total.
In symbols, the main step is:
delta_DFA(S, x) = epsilon-closure(union of delta_NFA(q, x) for every q in S)
If the NFA has no epsilon-moves, each epsilon-closure is simply the set itself, so the step costs nothing. When epsilon-moves are present it changes both the start state and every destination, and the second conversion below counts exactly that difference.
Fully worked NFA-to-DFA conversion
Consider an NFA over alphabet {a, b} with states {q0, q1, q2}. The start state is q0 and the accepting state is q2. Its transitions are:
delta(q0, a) = {q0, q1}
delta(q0, b) = {q0}
delta(q1, b) = {q2}
Every other transition is empty.
This NFA accepts strings ending in ab. State q0 keeps scanning any prefix. On an a, the NFA may also move to q1 and guess that this a starts the final ab. A following b reaches q2, which has no outgoing moves, so acceptance occurs only when that b ends the input.
There are no epsilon-moves, so the DFA start subset is:
A = {q0}
From A:
On a: delta(q0, a) = {q0, q1}, so create B = {q0, q1}.
On b: delta(q0, b) = {q0}, so return to A.
Now process B:
On a: delta(q0, a) union delta(q1, a) = {q0, q1} union empty = {q0, q1}, so stay at B.
On b: delta(q0, b) union delta(q1, b) = {q0} union {q2} = {q0, q2}, so create C = {q0, q2}.
Finally process C:
On a: delta(q0, a) union delta(q2, a) = {q0, q1}, so go to B.
On b: delta(q0, b) union delta(q2, b) = {q0}, so go to A.
C is accepting because it contains q2. A and B are not. Every input from every reachable subset already has a destination, so this conversion does not need the empty-set dead state.
The NFA has three states, so 2^3 = 8 subsets are mathematically possible. Only A, B and C are reachable. The constructed DFA therefore has 3 reachable states, not 8.
Verify the same example with a transition table
A table prevents missing an input edge and gives you a clean stopping rule. Add a row when a new subset appears; stop when every named subset has a completed row.
DFA state | NFA subset | On a | On b | Accepting? |
|---|---|---|---|---|
A | {q0} | B | A | No |
B | {q0, q1} | B | C | No |
C | {q0, q2} | B | A | Yes |
Check each column independently. The a-column is B, B, B because q0 appears in every reachable subset and its a-transition supplies {q0, q1}; q1 and q2 add nothing on a. In the b-column, only B includes q1, so only B can add q2 and reach C.
Test the machine on two strings. For aab, the DFA path is A to B to B to C, so it accepts. The string ends in ab. For aba, the path is A to B to C to B, so it rejects. It does not end in ab.
Epsilon-NFA to DFA: closure, the dead state and a second count
The first machine had no epsilon-moves and never ran out of destinations, so it exercised only part of the procedure. Take a second NFA over {a, b} with states {p0, p1, p2}, start state p0 and accepting state p2:
delta(p0, a) = {p1}
delta(p1, epsilon) = {p2}
delta(p2, b) = {p2}
Every other transition is empty.
This NFA accepts one a followed by any number of b symbols, the language ab*.
p0 has no epsilon-move, so the start subset is epsilon-closure({p0}) = P = {p0}. From P on a, delta(p0, a) = {p1}, and epsilon-closure({p1}) = {p1, p2} because p1 has an epsilon-move to p2. That gives Q = {p1, p2}, which is accepting. From P on b there is no move at all, so the destination is the empty subset D, the dead state.
Q on a has no move either, so it also goes to D. Q on b gives delta(p1, b) union delta(p2, b) = {p2}, and epsilon-closure({p2}) = {p2}, a new subset R = {p2}, also accepting. R on a goes to D, R on b returns to R, and D sends both symbols back to itself.
DFA state | NFA subset | On a | On b | Accepting? |
|---|---|---|---|---|
P | {p0} | Q | D | No |
Q | {p1, p2} | D | R | Yes |
R | {p2} | D | R | Yes |
D | empty set | D | D | No |
Four subsets are reachable out of 2^3 = 8, and one of them exists only because a DFA transition function must be total. Now compare Q and R: both accept, both go to D on a, and both go to R on b. They are equivalent, so the minimal DFA for ab* has 3 states, while subset construction hands you 4. Conversion answers how many states the construction produces; minimisation answers how few states are possible.
When the 2^n blow-up actually happens
The worst case is real, but it is not the answer to every conversion. For the binary language “the nth symbol from the end is a”, a compact NFA can guess which a is exactly n positions from the end. An equivalent DFA cannot guess. It must remember enough recent input to determine the nth-last symbol after the string stops.
For the small case “the second symbol from the end is a”, the minimal DFA needs 2^2 = 4 states. Those states encode the relevant recent-history possibilities. In the general family, the minimal DFA needs 2^n states, while the NFA uses about n + 1 states.
Read state-count wording carefully:
“Maximum possible states after conversion” points to the 2^n upper bound.
“States in the DFA obtained from this NFA” asks for reachable subsets.
“Minimum states in an equivalent DFA” may require minimising the reachable DFA after conversion.
Subset construction removes nondeterminism. It does not automatically guarantee that the resulting DFA is minimal.
The traps GATE plants
Forgetting epsilon-closure at the start or after a symbol transition.
Omitting the empty subset when a reachable state-symbol pair has no move.
Drawing all 2^n subsets instead of discovering only reachable ones.
Marking a subset final only when all members are final. Any one final NFA state is enough.
Counting equivalent reachable DFA states without performing minimisation when the question asks for a minimum.
Claiming that a DFA is more powerful. DFAs and NFAs recognise exactly the regular languages. Conversion changes representation and sometimes size, not expressive power.
How the exam tests conversion
Questions commonly ask for a particular subset transition, whether a subset is accepting, the number of reachable states, the minimum equivalent-DFA size or the worst-case count. Confirm the current Theory of Computation scope on the organising IIT's official GATE syllabus page.
Use Finite Automata: DFA vs NFA to review the model-level distinction, then solve Finite Automata MCQs on DFA, NFA and Minimization to practise conversions and state counts.
The short version and next step
A DFA state is a subset of NFA states. Start from the epsilon-closure of the NFA start, union moves for each input, take epsilon-closure again, and mark a subset accepting if it contains any final state. Draw reachable subsets only. Treat 2^n as a worst-case bound unless the wording asks for it.
KnowledgeGate's question bank carries about 1,000 Theory of Computation questions, including automata conversion. Drill them through the GATE Test Series, build the complete theory sequence with GATE Guidance by Sanchit Sir, and use the GATE preparation category to plan revision across subjects.
