NFA to DFA Conversion

NFA to DFA Conversion

Every NFA can be converted to an equivalent DFA using the subset construction algorithm (also called the powerset construction). The resulting DFA recognizes the exact same language, but may have exponentially more states.

The core idea: instead of tracking a single state (like a DFA does), we track a set of states that the NFA could be in simultaneously.

The Subset Construction

Start by computing the ε-closure of the NFA's start state (all states reachable via ε transitions). This becomes the DFA's start state. Then, for each DFA state (which is a set of NFA states) and each input symbol, compute the set of NFA states reachable. This set becomes a new DFA state.

NFA: M = ({q0, q1, q2}, {0,1}, δ, q0, {q2})

δ(q0, 0) = {q0, q1}
δ(q0, 1) = {q0}
δ(q1, 1) = {q2}

Step 1: DFA start state = ε-closure(q0) = {q0}

Step 2: Process {q0} on symbol 0:
  From q0 on 0 → {q0, q1}
  DFA state: {q0, q1}

Process {q0} on symbol 1:
  From q0 on 1 → {q0}
  DFA state: {q0}

Step 3: Process {q0, q1} on symbol 0:
  From q0 on 0 → {q0, q1}
  From q1 on 0 → {} (no transition)
  Result: {q0, q1}

Process {q0, q1} on symbol 1:
  From q0 on 1 → {q0}
  From q1 on 1 → {q2}
  Result: {q0, q2}

Step 4: Process {q0, q2} on symbol 0:
  From q0 on 0 → {q0, q1}
  From q2 on 0 → {}
  Result: {q0, q1}

Process {q0, q2} on symbol 1:
  From q0 on 1 → {q0}
  From q2 on 1 → {}
  Result: {q0}

Resulting DFA

The DFA states are: {q0}, {q0, q1}, {q0, q2}. Accept states are those containing an NFA accept state: {q0, q2}. The minimal number of DFA states is determined by the NFA structure — in the worst case, it's 2^n where n is the number of NFA states.

DFA from the construction:

  {q0}   --0--> {q0,q1}
  {q0}   --1--> {q0}
  {q0,q1} --0--> {q0,q1}
  {q0,q1} --1--> {q0,q2}  (accept)
  {q0,q2} --0--> {q0,q1}
  {q0,q2} --1--> {q0}

Accept: {{q0, q2}}

Why This Matters

The subset construction is how regex engines work in practice. An NFA-based regex is converted to a DFA for fast matching. While the DFA might be larger, it guarantees O(n) matching time for a string of length n — no backtracking needed.

Understanding this conversion also explains why some regex patterns cause "catastrophic backtracking" — they exploit NFA nondeterminism that becomes expensive when simulated with backtracking instead of DFA simulation.