NFA to DFA Conversion (Deep Dive)

NFA to DFA Conversion — Step by Step

This lesson provides a detailed, step-by-step walkthrough of converting an NFA to a DFA. Mastering this process is essential for understanding how nondeterminism can be eliminated, and it's the foundation of how regex engines work in practice.

The Algorithm

Given an NFA N = (Q, Σ, δ, q0, F), the DFA D = (Q', Σ, δ', q0', F') is constructed as follows:

Q' = P(Q) — each DFA state is a subset of NFA states. q0' = ε-closure(q0). F' = {S ∈ Q' | S ∩ F ≠ ∅} — any subset containing an NFA accept state. δ'(S, a) = ε-closure(∪_{q∈S} δ(q, a)).

Worked Example

Consider this NFA: Q = {q0, q1, q2}, Σ = {a, b}, start = q0, F = {q2}. Transitions: δ(q0, a) = {q0, q1}, δ(q0, b) = {q0}, δ(q1, b) = {q2}.

NFA Transition Table:
         a         b
  q0   {q0,q1}   {q0}
  q1   ∅         {q2}
  q2   ∅         ∅

DFA Construction:

1. Start state: {q0}

2. δ'({q0}, a) = ε-closure(δ(q0,a)) = {q0, q1}
   δ'({q0}, b) = ε-closure(δ(q0,b)) = {q0}

3. δ'({q0,q1}, a) = ε-closure(δ(q0,a) ∪ δ(q1,a))
                   = ε-closure({q0,q1} ∪ ∅)
                   = {q0, q1}
   δ'({q0,q1}, b) = ε-closure(δ(q0,b) ∪ δ(q1,b))
                   = ε-closure({q0} ∪ {q2})
                   = {q0, q2}

4. δ'({q0,q2}, a) = ε-closure({q0,q1} ∪ ∅) = {q0,q1}
   δ'({q0,q2}, b) = ε-closure({q0} ∪ ∅) = {q0}

5. No new states to process.

DFA States: {q0}, {q0,q1}, {q0,q2}
Accept states: {q0,q2} (contains q2)

DFA Transition Table

Reading the construction above, the DFA transition table is clean and deterministic:

DFA Transition Table:
           a         b
  {q0}    {q0,q1}   {q0}
  {q0,q1} {q0,q1}   {q0,q2}  ← accept
  {q0,q2} {q0,q1}   {q0}

Accept: {q0, q2}

Minimization

The DFA produced by subset construction may not be minimal. Some states might be unreachable from the start state, or some states might be equivalent (indistinguishable). DFA minimization removes redundant states using partition refinement, producing the smallest possible DFA for the language.

The Hopcroft algorithm is the standard approach for DFA minimization. It runs in O(n log n) time and produces a unique minimal DFA for any regular language.