NFA → DFA Conversion

How NFA → DFA Conversion works

Subset construction turns a nondeterministic automaton into a deterministic one by making each DFA state stand for a *set* of NFA states — every state the NFA could be in at once. The start state is the epsilon-closure of the NFA start state: the start state plus everything reachable from it on epsilon moves alone. From there the algorithm is a worklist. Take an unprocessed set, and for each symbol in the alphabet collect every NFA state reachable from any member on that symbol, then take the epsilon-closure of that collection. The result is one DFA transition. If it is a set you have not seen before, add it to the worklist and give it a name. Repeat until nothing new appears. A DFA state is accepting exactly when the set it represents contains at least one NFA accepting state. The language is unchanged; only the bookkeeping moves from run time into the transition table.

Pseudocode

subsetConstruction(NFA N):
    start = epsilonClosure({N.start})
    DFAStates = { start }          // unmarked
    worklist  = [ start ]

    while worklist is not empty:
        T = worklist.pop()
        for each symbol a in alphabet:            // epsilon is NOT a symbol here
            move   = { s | t in T, s in N.delta(t, a) }
            U      = epsilonClosure(move)
            if U is empty: continue               // or route to a dead state
            if U not in DFAStates:
                DFAStates.add(U)
                worklist.push(U)
            DFA.delta(T, a) = U

    for each T in DFAStates:
        if T contains any accepting state of N:
            mark T accepting
    return DFA

epsilonClosure(S):
    stack = S; closure = S
    while stack not empty:
        t = stack.pop()
        for each u in N.delta(t, epsilon):
            if u not in closure:
                closure.add(u); stack.push(u)
    return closure

Time and space complexity

Time

O(2^n · |Σ| · n) worst case

Space

O(2^n · n)

A DFA state is a subset of the n NFA states, so there are at most 2^n of them; each needs one transition per alphabet symbol, and computing that transition scans the subset. Most textbook NFAs produce far fewer than 2^n reachable subsets — the blow-up is a worst case, not the usual case.

Worked example

NFA over {a, b} with states q0, q1, q2. q0 --a--> q0, q0 --a--> q1, q0 --b--> q0, q1 --b--> q2. q2 is accepting. No epsilon moves. (This accepts strings ending in "ab".)

1. Startclosure({q0}) = {q0}. Name it A.
2. A on aFrom q0 on a we reach q0 and q1 → {q0, q1}. New — call it B.
3. A on bFrom q0 on b we reach q0 → {q0} = A. Self-loop.
4. B on aq0 gives {q0, q1}; q1 has no a-move → {q0, q1} = B.
5. B on bq0 gives q0; q1 gives q2 → {q0, q2}. New — call it C.
6. C on aq0 gives {q0, q1}; q2 has no a-move → B.
7. C on bq0 gives q0; q2 has no b-move → A.

Three DFA states: A = {q0}, B = {q0,q1}, C = {q0,q2}. C is the only accepting state because it is the only subset containing q2. Worklist empty, conversion done.

Common exam mistakes

• Forgetting the epsilon-closure on the start state. If the NFA can slide out of its start state on epsilon, the DFA start state is a set, not a singleton.
• Taking the closure before the move instead of after. The order is move on the symbol first, then close over epsilon — closure(move(T, a)), not move(closure(T), a).
• Treating epsilon as an alphabet symbol and giving the DFA an epsilon column. A DFA has no epsilon transitions at all.
• Marking a subset accepting only when every member is accepting. One accepting NFA state in the subset is enough.
• Dropping the empty set instead of handling it. If you need a total transition function, the empty set is a real (dead, non-accepting) trap state that loops to itself on everything.

Frequently asked questions

Related simulators