From NFA to DFA: the subset construction

Advanced

Introduction

An NFA is easy to design, while a DFA is easy to run: one move per symbol, no sets, no guessing. The subset construction gives us both. It turns any NFA into a DFA that accepts exactly the same strings, which proves that nondeterminism adds convenience but no power.

The idea is the one you already used to simulate an NFA: track the set of states it could be in. In the subset construction, each such set becomes a single state of a new DFA.

How it works

Given an NFA with states Q, build a DFA as follows:

  1. The DFA's start state is the ε-closure of the NFA's start state, a set.
  2. For a DFA state S (a set) and a symbol c, the move is the ε-closure of the union of the NFA's moves on c from every state in S.
  3. A DFA state is accepting if it contains at least one NFA accepting state.

There are 2ⁿ subsets of n states, but most are never reached. So we build only the reachable ones with a breadth-first search: put the start set in a queue; take a set out, compute its move on every symbol, and add any new set to the queue. When the queue is empty, every reachable state has its full row in the table.

The empty set ∅ may appear: it means no NFA path is alive. In the DFA it is a dead state that loops to itself.

Sets cannot be dictionary keys in Python, because they can change, so use frozenset, the unchangeable version.

How big can it get? For "the n-th symbol from the end is a", the NFA has n + 1 states, but the DFA must remember the last n symbols, so it needs 2ⁿ states. This state explosion is why some tools keep the NFA and simulate it, rather than converting.

Syntax

start = frozenset(closure({q0}))
seen, queue = {start}, [start]
while queue:
    S = queue.pop(0)
    for c in alphabet:
        T = frozenset(closure(set().union(*(delta.get((q, c), set()) for q in S))))
        table[(S, c)] = T
        if T not in seen:
            seen.add(T); queue.append(T)

Example

delta = {
    (0, "a"): {0, 1}, (0, "b"): {0},
    (1, "a"): {2}, (1, "b"): {2},
    (2, "a"): {3}, (2, "b"): {3},
}
alphabet = "ab"
start = frozenset({0})
seen = {start}
queue = [start]
table = {}
while queue:
    S = queue.pop(0)
    for c in alphabet:
        T = frozenset(set().union(*(delta.get((q, c), set()) for q in S)))
        table[(S, c)] = T
        if T not in seen:
            seen.add(T)
            queue.append(T)


def name(S):
    return "{" + ",".join(map(str, sorted(S))) + "}"


print("DFA states:", len(seen))
for S in sorted(seen, key=lambda s: (len(s), sorted(s))):
    mark = "*" if 3 in S else " "
    print(mark, name(S), "a->", name(table[(S, "a")]), "b->", name(table[(S, "b")]))
Open in compiler

Line by line

  1. The NFA is the "third symbol from the end is a" machine from the previous lesson; it has no ε-moves, so no closure is needed.
  2. The search starts from {0} and builds the move on a and b for every set it meets.
  3. Exactly 8 = 2³ sets are reachable: the DFA must remember the last three symbols.
  4. The rows are printed shortest set first. A * marks sets containing 3, the accepting NFA state, so those DFA states accept.
  5. For example {0,1} on a goes to {0,1,2}: from 0 on a you may reach 0 or 1, and from 1 on a you reach 2.

Expected result

DFA states: 8
  {0} a-> {0,1} b-> {0}
  {0,1} a-> {0,1,2} b-> {0,2}
  {0,2} a-> {0,1,3} b-> {0,3}
* {0,3} a-> {0,1} b-> {0}
  {0,1,2} a-> {0,1,2,3} b-> {0,2,3}
* {0,1,3} a-> {0,1,2} b-> {0,2}
* {0,2,3} a-> {0,1,3} b-> {0,3}
* {0,1,2,3} a-> {0,1,2,3} b-> {0,2,3}

In the real world

Lexer generators such as lex and flex compile regular expressions to an NFA, run the subset construction, and then minimise the result into a fast table-driven DFA. Some regex engines, such as RE2, build DFA states lazily while matching, which avoids exploring states the input never reaches.

Common mistakes

  • Using set as a dictionary key: Python refuses; use frozenset.
  • Forgetting the ε-closure of the start set or of each move.
  • Marking a set accepting only if all its states accept: one accepting state is enough.
  • Building all 2ⁿ subsets instead of only the reachable ones.

Best practices

  • Build states with a queue so that each set is processed exactly once.
  • Give each built state a readable name such as {0,2} when printing tables.
  • Count the states as you go, so that a state explosion is easy to notice.

Summary

The subset construction turns an NFA into an equivalent DFA whose states are reachable sets of NFA states. A set's move is the closure of the union of its members' moves, and it accepts if it contains an accepting state. The result can be exponentially larger, but it proves that NFAs and DFAs recognise the same class of languages.

Quick check

1. In the subset construction, a DFA state is…
2. When is a built DFA state accepting?
3. An NFA has 5 states. At most how many states can its subset DFA have?
4. Why use frozenset rather than set for DFA states in Python?

Key takeaways

  • A DFA state is a set of NFA states; its move on c is the union of their moves.
  • Build only the reachable sets, with a queue, starting from the start's closure.
  • NFAs and DFAs recognise exactly the same languages: the regular languages.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.