NFA to DFA Conversion: Subset Construction, Worked Example, and Exam Traps

Subset construction is easy to memorise as a rule, but one branching transition is enough to make the table confusing. The real task is to track every NFA state that can be active after the same input prefix. Here, we will carry one conversion through every reachable subset, test the result with strings, and minimise it separately. The goal is not to draw every possible subset, but to discover only those reachable from the start state.

What NFA to DFA conversion preserves

In a nondeterministic finite automaton (NFA), a state-symbol pair may lead to zero, one, or several states. In a deterministic finite automaton (DFA), every state-symbol pair has exactly one next state.

Subset construction reconciles these rules by making each DFA state represent a set of NFA states. After any input prefix, that set contains every NFA state in which the original machine could be active. This is the invariant behind the whole conversion.

The NFA and the constructed DFA therefore recognise the same language. An NFA with n states has at most 2^n possible subsets, but the DFA contains only the subsets reachable from its start state. Determinisation does not guarantee a minimum-state DFA. Minimisation is a later operation.

If that distinction is still unclear, first review Finite Automata: DFA vs NFA and Subset Construction.

The subset-construction algorithm, including epsilon moves

Use a work queue so that no reachable subset is missed or processed twice:

1. Compute epsilon-closure({start state}) and name this set as the DFA start state.

2. For each alphabet symbol, take the union of the NFA destinations of every state in the current subset.

3. Take the epsilon-closure of that union.

4. Add a new row and enqueue the result only if that subset has not appeared before.

5. Continue until no unprocessed subset remains.

6. Mark a DFA subset accepting if it contains at least one NFA accepting state.

For a small epsilon check, take states {p0,p1,p2}, alphabet {a,b}, start p0, and accepting state p2. Let p0 have an epsilon edge to p1, with p1 --a--> p1 and p1 --b--> p2; every other move is empty. Then:

• epsilon-closure({p0})={p0,p1}

• on a: epsilon-closure({p1})={p1}

• on b: epsilon-closure({p2})={p2}

The main example has no epsilon edges, so ordinary destination sets replace closures. If any reachable move produces empty-set, include it as a DFA state and loop it on every symbol. Do not add it when no reachable move produces it.

Worked example: fix the NFA before doing subset arithmetic

Use Q={q0,q1,q2}, Sigma={0,1}, start state q0, and accepting set F={q2}.

The table also explains the language. State q0 keeps the machine alive on every symbol. Reading 0 may start a second branch at q1, and a later 1 moves that branch to accepting state q2. Once reached, q2 remains active. The NFA therefore accepts exactly the binary strings containing substring 01.

Learners who want this conversion inside the full finite-automata sequence can use the Theory of Computation / Automata Theory course.

Convert the NFA row by row

Start with A={q0} and process subsets in discovery order.

• From A, on 0: {q0,q1}=B. On 1: {q0}=A.

• From B={q0,q1}, on 0: {q0,q1} union empty-set=B. On 1: {q0} union {q2}={q0,q2}=C.

• From C={q0,q2}, on 0: {q0,q1} union {q2}={q0,q1,q2}=D. On 1: {q0} union {q2}=C.

• From D={q0,q1,q2}, on 0: {q0,q1} union empty-set union {q2}=D. On 1: {q0} union {q2} union {q2}=C.

The completed DFA table is:

Both C and D are accepting because each contains q2. Processing D creates no new subset, so the queue closes. Although 2^3=8 subsets are theoretically possible, only four are reachable. The subsets empty-set, {q1}, {q2}, and {q1,q2} do not belong in this constructed DFA.

Validate the DFA with actual strings

A few traces test the table against the claimed language.

Now check independently with NFA active-state sets. For 01, the trace is {q0} -> {q0,q1} -> {q0,q2}, so q2 is active and the string is accepted. For 10, it is {q0} -> {q0} -> {q0,q1}. State q2 is absent, so the string is rejected. Every accepted sample contains 01, while every rejected sample lacks it.

Determinisation is not minimisation

Begin partition refinement with non-accepting states {A,B} and accepting states {C,D}. States A and B must split: input 1 keeps A in the non-accepting partition, but sends B to accepting state C.

States C and D stay together. On both 0 and 1, each moves within the accepting partition. Merge them into one accepting state F.

The three counts are distinct: the original NFA has 3 states, the reachable subset DFA has 4, and the minimum DFA has 3. DFA Minimization for GATE: Minimum States, Step by Step covers the later operation in detail. Always complete determinisation before minimising.

How exam-style questions test the conversion, and where errors happen

Typical tasks ask you to complete a subset-table row, count reachable DFA states, identify accepting subsets, trace a string, apply epsilon-closures, or distinguish the converted-state count from the minimum-state count. These are different checks on the same invariant.

The safest working habit is to write one row per discovered subset and keep an explicit queue. It prevents guessed transitions, duplicated subset names, and premature merging.

Short version and next step

• Start from the start-state closure.

• Union destinations symbol by symbol.

• Enqueue only new reachable subsets.

• Mark every subset containing an NFA final state as accepting.

• Minimise after determinisation, not during it.

For subject-wise browsing, use the CS Fundamentals category. Readers seeking a broader core-CS route can choose Zero to Hero. Then redraw this NFA from its table, rebuild A, B, C, and D without looking, and verify 001, 10, and 1011 against both machines.