NFA to DFA Conversion (Subset Construction)

Why convert?

An NFA can guess, so it is easy to design. A DFA has exactly one move for each symbol, so it is easy to run. Surprisingly they recognise exactly the same languages (the regular languages), and the subset construction proves it by converting any NFA to a DFA.

The idea

After reading some input an NFA may be in several states at once. The DFA simply remembers that whole set as its single current state.

start  ← { NFA start state }
queue  ← [ start ]
while queue is not empty:
    S ← next subset
    for each symbol c:
        T ← union of δ(q, c) for every q in S
        δD(S, c) ← T
        if T is new: add it to the queue
accepting DFA states = subsets that contain an accepting NFA state

Worked example: strings ending in “ab”

NFA: q0 loops on a and b; on a it may also go to q1; q1 goes to q2 on b; q2 accepts.

Three DFA states, and every NFA path is tracked at once. The reading aab ends in {q0, q2}, which contains the accepting q2, so the string is accepted.

The blow-up

An n-state NFA can need 2ⁿ DFA states. The language “the second symbol from the end is a” has a 3-state NFA but its DFA needs 4 states, and “the n-th symbol from the end is a” needs 2ⁿ. NFAs can be exponentially smaller, and you can shrink the result afterwards with DFA minimization.

Code

def subset_construction(delta, start, accepting, alphabet):
    start_set = frozenset([start])
    table, queue = {}, [start_set]
    while queue:
        S = queue.pop()
        if S in table:
            continue
        table[S] = {}
        for c in alphabet:
            T = frozenset(t for q in S for t in delta.get((q, c), ()))
            table[S][c] = T
            queue.append(T)
    final = {S for S in table if S & accepting}
    return table, final

Common mistakes

• Adding all 2ⁿ subsets instead of only the reachable ones.
• Forgetting the empty set as a dead state when a move does not exist.
• Marking a subset accepting only if all its members accept. One accepting member is enough.
• Mixing up the start state: it is the subset containing only the NFA start state (plus its ε-closure if ε-moves exist).