Chapter 07 of 34

NFA to DFA Conversion (Subset Construction)

In Nondeterministic Finite Automata (NFA) we ran NFAs by tracking the set of states the machine could be in. At every step that set was completely determined by the previous set and the input symbol. There was no guessing left in it at all.

That observation is the whole trick behind converting an NFA into a DFA: make each set of NFA states a single DFA state. Since an NFA with n states has only 2n possible sets, the resulting machine is finite, so it is a genuine DFA.

Subset construction (powerset construction): given an NFA N = (Q, Σ, δ, q0, F), build a DFA whose states are subsets of Q, whose start state is {q0}, whose transition on symbol a from subset S is the union of δ(p, a) for all p in S, and whose final states are the subsets containing at least one state of F.

In this chapter we will learn the algorithm, apply it to four NFAs step by step, see when the DFA really becomes exponentially large, and understand why the construction is correct. Every table in this chapter was produced by a program that performs the construction, and each resulting DFA was checked against its language on all strings up to length 12. (ε-moves are handled in the next chapter, Epsilon-NFA & Epsilon-Closure; here all NFAs are ε-free.)


The Construction

Given NFA N = (Q, Σ, δ, q0, F), the DFA D = (QD, Σ, δD, S0, FD) is:

Q_D          = all subsets of Q              (at most 2^|Q| of them)
S_0          = { q0 }
δ_D(S, a)    = ⋃ δ(p, a)   for all p ∈ S     (and δ_D(∅, a) = ∅)
F_D          = { S ⊆ Q : S ∩ F ≠ ∅ }

Two details trip up many students:

  • The empty set ∅ is a legal DFA state. It appears whenever none of the NFA states in S has a move on a. It is a dead (trap) state: non-final, and it goes to itself on every symbol.

  • A subset is final if it contains any final NFA state, not only if it equals F.

Lazy construction: only build what you can reach

Writing down all 2n subsets is wasteful, because most of them are usually unreachable from {q0}. In exams and in real tools we build only the reachable ones, using a worklist:

start      = { q0 }
D_states   = [ start ]          (all discovered subsets)
unmarked   = [ start ]          (subsets whose rows are not filled yet)

while unmarked is not empty:
    take S from unmarked
    for each symbol a in Σ:
        T = ⋃ δ(p, a) for p ∈ S
        δ_D(S, a) = T
        if T is not in D_states:
            add T to D_states and to unmarked

final states = subsets in D_states containing a state of F

Each row of the DFA table is filled exactly once, and new rows are only created for subsets that actually appear on the right side.


Example 1: Strings Ending with 01

The NFA from the previous chapter (Σ = {0, 1}):

NFA state

0

1

→ q0

{q0, q1}

{q0}

q1

∅

{q2}

* q2

∅

∅

Step 1. Start with {q0}.

δ_D({q0}, 0) = δ(q0,0)                 = {q0, q1}     ← new
δ_D({q0}, 1) = δ(q0,1)                 = {q0}

Step 2. Process {q0, q1}.

δ_D({q0,q1}, 0) = δ(q0,0) ∪ δ(q1,0) = {q0,q1} ∪ ∅    = {q0, q1}
δ_D({q0,q1}, 1) = δ(q0,1) ∪ δ(q1,1) = {q0} ∪ {q2}     = {q0, q2}   ← new

Step 3. Process {q0, q2}.

δ_D({q0,q2}, 0) = {q0,q1} ∪ ∅ = {q0, q1}
δ_D({q0,q2}, 1) = {q0}    ∪ ∅ = {q0}

No new subsets appear, so we stop. {q0, q2} contains the final state q2, so it is final.

DFA state

0

1

→ A = {q0}

B

A

B = {q0, q1}

B

C

* C = {q0, q2}

B

A

  ──►  A ──0──► B ──1──► ((C))
       ⟲ 1      ⟲ 0

  remaining arrows:   C ──0──► B      C ──1──► A

Only 3 of the 23 = 8 subsets were reachable. Read the states as memories: A = "last symbol was not 0 (or nothing read)", B = "last symbol was 0", C = "last two symbols were 01". That is exactly the DFA you would design by hand.


Example 2: Where the Dead State Comes From

NFA for strings over {a, b} that start with a and end with b:

NFA state

a

b

→ q0

{q1}

∅

q1

{q1}

{q1, q2}

* q2

∅

∅

{q0}      a → {q1}                    b → ∅           ← new: dead state
{q1}      a → {q1}                    b → {q1,q2}     ← new
∅         a → ∅                       b → ∅
{q1,q2}   a → {q1} ∪ ∅ = {q1}         b → {q1,q2} ∪ ∅ = {q1,q2}

DFA state

a

b

→ {q0}

{q1}

∅

{q1}

{q1}

{q1, q2}

∅

∅

∅

* {q1, q2}

{q1}

{q1, q2}

The DFA has 4 states, and one of them is ∅. The NFA did not need a trap state (a b at the start just killed the path), but a DFA must have a move for every symbol, so ∅ plays that role. Always count ∅ when a question asks for the number of DFA states, unless it explicitly says to ignore the dead state.


Example 3: An NFA Given as a Table

Exam questions often give an NFA as a bare table. Σ = {0, 1}, start state p, final state s:

NFA state

0

1

→ p

{p, q}

{p}

q

{r}

{r}

r

{s}

∅

* s

{s}

{s}

Before converting, it helps to read the NFA: p waits, then p –0→ q –(0 or 1)→ r –0→ s, and s loops forever. So it accepts strings that contain 0x0 for some symbol x, i.e. contain 000 or 010.

Now the worklist, naming each subset as it is discovered:

S0 = {p}          0: {p,q}                          = S1 (new)
                  1: {p}                            = S0
S1 = {p,q}        0: {p,q} ∪ {r}       = {p,q,r}    = S2 (new)
                  1: {p}   ∪ {r}       = {p,r}      = S3 (new)
S2 = {p,q,r}      0: {p,q} ∪ {r} ∪ {s} = {p,q,r,s}  = S4 (new)
                  1: {p}   ∪ {r} ∪ ∅   = {p,r}      = S3
S3 = {p,r}        0: {p,q} ∪ {s}       = {p,q,s}    = S5 (new)
                  1: {p}   ∪ ∅         = {p}        = S0
S4 = {p,q,r,s}    0: {p,q,r,s}                      = S4
                  1: {p} ∪ {r} ∪ ∅ ∪ {s} = {p,r,s}  = S6 (new)
S5 = {p,q,s}      0: {p,q} ∪ {r} ∪ {s} = {p,q,r,s}  = S4
                  1: {p} ∪ {r} ∪ {s}   = {p,r,s}    = S6
S6 = {p,r,s}      0: {p,q} ∪ {s} ∪ {s} = {p,q,s}    = S5
                  1: {p} ∪ ∅ ∪ {s}     = {p,s}      = S7 (new)
S7 = {p,s}        0: {p,q} ∪ {s}       = {p,q,s}    = S5
                  1: {p} ∪ {s}         = {p,s}      = S7

DFA state

Subset

0

1

→ S0

{p}

S1

S0

S1

{p, q}

S2

S3

S2

{p, q, r}

S4

S3

S3

{p, r}

S5

S0

* S4

{p, q, r, s}

S4

S6

* S5

{p, q, s}

S4

S6

* S6

{p, r, s}

S5

S7

* S7

{p, s}

S5

S7

8 reachable subsets out of 16. Every subset contains p, because p has a self-loop on both symbols, so p is always a possible state. (That is a handy sanity check: if the start state loops on every symbol, every reachable subset contains it.)

Is this DFA as small as possible? No. The four final states S4–S7 all mean "0x0 has already been seen", and from then on everything is accepted, so they can be merged into one. The minimal DFA has 5 states. Subset construction gives a correct DFA, not necessarily the smallest; shrinking it is the job of DFA Minimization.


Example 4: The Exponential Blow-Up

The NFA for "third symbol from the end is 1" had 4 states (q0 loops on 0, 1; q0 –1→ q1 –0,1→ q2 –0,1→ q3, final q3). Subset construction gives:

DFA state

0

1

→ {q0}

{q0}

{q0, q1}

{q0, q1}

{q0, q2}

{q0, q1, q2}

{q0, q2}

{q0, q3}

{q0, q1, q3}

{q0, q1, q2}

{q0, q2, q3}

{q0, q1, q2, q3}

* {q0, q3}

{q0}

{q0, q1}

* {q0, q1, q3}

{q0, q2}

{q0, q1, q2}

* {q0, q2, q3}

{q0, q3}

{q0, q1, q3}

* {q0, q1, q2, q3}

{q0, q2, q3}

{q0, q1, q2, q3}

All 8 subsets that contain q0 are reachable. There is a beautiful way to read them: q1 ∈ S means "the last symbol was 1", q2 ∈ S means "the second-last was 1", q3 ∈ S means "the third-last was 1". So each subset is exactly a record of the last three symbols, which is what any DFA for this language must remember.

Generalising to "the n-th symbol from the end is 1" (computed by program):

n

NFA states

DFA states from subset construction

Minimal DFA states

1

2

2

2

2

3

4

4

3

4

8

8

4

5

16

16

5

6

32

32

6

7

64

64

Here the blow-up cannot be avoided by any cleverness: the minimal DFA really has 2n states. So the 2n bound of subset construction is tight, up to the small difference between n and n + 1 states.


Why Subset Construction Is Correct

The claim is that for every string w:

δ̂_D({q0}, w) = δ̂_N(q0, w)

i.e. the DFA state reached on w is exactly the set of NFA states reachable on w. Proof by induction on |w|:

  • Base, w = ε: both sides are {q0}.

  • Step, w = xa: assume δ̂D({q0}, x) = δ̂N(q0, x) = S. Then δ̂D({q0}, xa) = δD(S, a) = ⋃p ∈ S δ(p, a), which is precisely the definition of δ̂N(q0, xa).

Then w ∈ L(D) ⟺ δ̂D({q0}, w) ∈ FD ⟺ δ̂N(q0, w) ∩ F ≠ ∅ ⟺ w ∈ L(N). So L(D) = L(N).

Theorem: a language is accepted by some NFA if and only if it is accepted by some DFA. (DFA → NFA is trivial; NFA → DFA is subset construction.)


Cost of the Construction

Quantity

Bound

DFA states (full construction)

exactly 2n for an n-state NFA

DFA states (lazy, reachable only)

at most 2n; often close to n in practice

Work per DFA row

a union over up to n NFA states, for each of the |Σ| symbols

Total time (worst case)

O(2n · |Σ| · n2) with simple set operations

This is why practical tools sometimes simulate the NFA directly (tracking a set of states per input symbol, cheap to build, slower per character) and sometimes convert to a DFA (possibly expensive to build, but one table lookup per character). Lexer generators such as Lex/Flex convert to a DFA because the lexer runs on huge inputs many times.


Exam Shortcuts

  • Use lazy construction. Never list all 2n subsets unless the question asks for the "full" powerset DFA.

  • Watch for ∅. If some NFA row has an empty entry, ∅ will probably appear; include it and give it self-loops.

  • Start state with a self-loop on everything means every subset contains it; you only need to track the other states.

  • Check final states by scanning each subset for any NFA final state.

  • Sanity-check with one string: run it on the NFA (set method) and on your DFA; they must give the same answer.


Common Mistakes

  • Forgetting the dead state ∅, or forgetting that it needs self-loops on all symbols.

  • Marking only the subset equal to F as final. Any subset containing a final state is final.

  • Treating {p, q} and {q, p} as different states. They are the same set; order does not matter.

  • Counting unreachable subsets when the question asks for the DFA "obtained by subset construction" in the usual (reachable) sense.

  • Assuming the result is minimal. It is correct but may have redundant states (Example 3 gave 8 states; the minimum is 5).

  • Assuming the DFA must always be exponentially larger. Often it is the same size or only slightly bigger (Example 1: 3 states both ways).


Practice and GATE-Style Questions

Q1. Convert this NFA over {a, b} (start q0, final q0) to a DFA and count its states: δ(q0, a) = {q1, q2}, δ(q0, b) = ∅, δ(q1, a) = {q0}, δ(q1, b) = {q1}, δ(q2, a) = ∅, δ(q2, b) = {q0, q2}.

→* {q0}         a: {q1,q2}        b: ∅
   {q1,q2}      a: {q0}           b: {q1} ∪ {q0,q2} = {q0,q1,q2}
   ∅            a: ∅              b: ∅
 * {q0,q1,q2}   a: {q1,q2} ∪ {q0} ∪ ∅ = {q0,q1,q2}
                b: ∅ ∪ {q1} ∪ {q0,q2} = {q0,q1,q2}

4 states (including ∅). Final states: {q0} and {q0, q1, q2}. The start state is final, so ε is accepted.

Q2. An NFA has 4 states. What is the maximum number of states in the DFA produced by subset construction? What is the minimum?

Maximum 24 = 16. With lazy (reachable-only) construction the minimum is 1: for example, if δ(q0, a) = {q0} for every symbol a, the only reachable subset is {q0}, whatever the other three states do. (With the full construction you always write all 16 subsets.)

Q3. The NFA for strings over {0, 1} ending in 01 has 3 states. How many states does the DFA from subset construction have, and is it minimal?

3 states ({q0}, {q0, q1}, {q0, q2}), and yes, it is minimal: the three states remember "no useful suffix", "ended in 0" and "ended in 01", and these behave differently (for example on suffixes 1 and ε).

Q4. Which language over {0, 1} needs 2n DFA states but only n + 1 NFA states?

The set of strings whose n-th symbol from the end is 1 (equivalently, (0 + 1)* 1 (0 + 1)n−1). The DFA must remember the last n symbols, and all 2n combinations are distinguishable.

Q5. In subset construction, when is a DFA state S final?

When S ∩ F ≠ ∅, i.e. S contains at least one final state of the NFA.

Q6. Interview: why can't we apply the same idea to make every PDA deterministic?

Subset construction works because a finite automaton's whole configuration is just its state, and there are finitely many sets of states. A PDA's configuration also includes an unbounded stack, so the set of possible configurations is infinite and cannot be folded into finitely many states. Indeed, deterministic PDAs accept strictly fewer languages than nondeterministic ones.


Summary

  • Each DFA state is a set of NFA states; the start state is {q0}.

  • δD(S, a) = union of δ(p, a) over p ∈ S.

  • A DFA state is final if it contains any NFA final state.

  • ∅ is the dead state; include it when it is reachable.

  • Build only reachable subsets with a worklist (lazy construction).

  • At most 2n states; the bound is tight ("n-th symbol from the end").

  • The result is correct but not always minimal; minimise it afterwards if needed.

  • Subset construction proves that NFAs and DFAs accept exactly the same languages.

An NFA's "maybe here, maybe there" becomes a DFA's "I am in this set". Nondeterminism disappears, at the possible cost of many more states.