Skip to content
Tutorials Center
My learning

Topics

Lesson 8 of 59 · Finite Automata

Converting an NFA to a DFA (Subset Construction)

Learn the subset construction that converts any NFA or ε-NFA into an equivalent DFA, with step-by-step tables, a Python implementation and the exponential blowup.

NFAs are easy to design but a computer needs a deterministic recipe. The subset construction (also called the powerset construction) shows that nondeterminism adds no power: for every NFA there is a DFA that accepts exactly the same language. The idea is the same one you used to simulate an NFA: keep track of the set of all states the NFA could be in. If you make each such set a single DFA state, the nondeterminism disappears.

The construction

Given an NFA N = (Q, Σ, δ, q0, F), build a DFA D whose states are subsets of Q:

  1. Start state: {q0} (or ECLOSE(q0) if N has ε-moves).
  2. Transitions: for a DFA state S (a set) and a symbol a, the next state is the set of all states N can reach from any member of S by reading a: δ_D(S, a) = ∪ over q in S of δ(q, a). With ε-moves, take the ε-closure of this union.
  3. Accepting states: every subset that contains at least one accepting state of N.
  4. Only build the subsets you can actually reach from the start. In practice this is usually far fewer than all 2^|Q| subsets.

The empty set ∅ is a legitimate DFA state: it is the dead state, reached when every branch of the NFA got stuck.

A worked example by hand

Take the NFA over {a, b} that accepts strings whose second symbol from the right is a. States q0, q1, q2; q0 loops on a and b and also moves to q1 on a; q1 moves to q2 on a or b; q2 accepts.

Start at {q0}.

DFA state on a on b
-> {q0} {q0, q1} {q0}
{q0, q1} {q0, q1, q2} {q0, q2}
* {q0, q1, q2} {q0, q1, q2} {q0, q2}
* {q0, q2} {q0, q1} {q0}

Compute the second row: from {q0, q1} on a, q0 goes to {q0, q1} and q1 goes to {q2}, so the union is {q0, q1, q2}. On b, q0 goes to {q0} and q1 to {q2}, giving {q0, q2}. Four reachable subsets cover everything. Compare this to a hand design: a DFA for this language really does need 4 states, so the subset construction gave a minimal machine here.

flowchart LR
    start(( )) --> A
    A["{q0}"] -->|"a"| B["{q0,q1}"]
    A -->|"b"| A
    B -->|"a"| C((("{q0,q1,q2}")))
    B -->|"b"| D((("{q0,q2}")))
    C -->|"a"| C
    C -->|"b"| D
    D -->|"a"| B
    D -->|"b"| A

Each DFA state is a set of NFA states. The double circles contain the NFA's accepting state q2.

Implementing it

A set of states is not hashable in Python, so we use frozenset as the DFA state name. The function below handles ε-moves through an ε-closure (symbol "").

Python Subset construction in Python

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The printed table matches the hand computation: four states, with the two sets containing q2 marked as accepting. Because this function builds only reachable subsets, it never creates the other 4 of the 8 possible subsets.

Handling ε-moves and measuring blowup

The same function converts ε-NFAs, because it takes the ε-closure of the start state and of every computed set. Next we convert the a*b*c* ε-NFA from the previous lesson, then measure how big the DFA gets for the family "the n-th symbol from the right is a", whose NFA has only n + 1 states.

Python From epsilon-NFA to DFA, and exponential growth

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The a*b*c* DFA has four states: three useful subsets and the empty dead set ∅ (reached after ba, cb and the like). For the second family, the DFA state count doubles with each increase of n, exactly 2^n, while the NFA grows by one state. So the exponential blowup in the worst case is real, not just a theoretical bound: some languages need an NFA much smaller than any DFA.

Why the construction is correct

By induction on the length of w: after reading w, the DFA is in exactly the set of states in which the NFA could be after reading w. At the end the DFA accepts iff that set includes an accepting NFA state, iff some NFA path accepts. So L(D) = L(N). This proves a central theorem: NFAs, ε-NFAs and DFAs all recognize exactly the regular languages.

Check your understanding

Quick check · 5 questions

of 5 answered You scored / 5 · perfect!

  1. 1. What are the states of the DFA built by the subset construction?

    Each DFA state stands for the set of NFA states the NFA could be in after reading the input so far.
  2. 2. Which DFA states are accepting?

    The NFA accepts if some path ends in an accepting state, so a subset accepts when it includes at least one accepting NFA state.
  3. 3. An NFA has 5 states. What is the maximum number of states in the equivalent subset-construction DFA?

    There are 2^5 = 32 subsets of 5 states, and that many DFA states may be needed in the worst case.
  4. 4. What does the empty-set DFA state represent?

    ∅ means no NFA state is possible any more. It is non-accepting and loops to itself on every symbol.
  5. 5. With ε-moves, what changes in the construction?

    ε-moves are free, so every set must be extended with all states reachable by ε-arrows, including the start set.

Summary

  • The subset construction turns an NFA (or ε-NFA) into a DFA whose states are sets of NFA states.
  • Start from ECLOSE(q0); step with a symbol, then take the ε-closure; accept any set containing an NFA accepting state.
  • Build only reachable subsets; ∅ is the dead state.
  • The DFA can be exponentially larger (the n-th symbol from the right needs 2^n states), so nondeterminism buys succinctness but not power.

Next: Operations on DFAs