CampusFlow
Theory of Comp.NFA → DFA Conversion

NFA → DFA Conversion

Convert Non-deterministic Finite Automata to Deterministic Finite Automata using the subset construction algorithm. Build or load an NFA with ε-transitions, then visualize each step of the conversion.

NFA

abaa,bq0q1q2
Click a state

Transition

from ?to ?

Test NFA

DFA

Build an NFA and click Convert

Subset Construction Algorithm

ℹ️

How It Works

  1. Compute the ε-closure of the NFA's start state — this becomes the DFA's start state.
  2. For each new DFA state (an NFA subset), compute the transition for each alphabet symbol: take the union of all NFA states reachable from the subset on that symbol, then compute the ε-closure of the result.
  3. If this produces a new subset not yet seen, add it as a new DFA state.
  4. A DFA state is accepting if any NFA state in its subset is accepting.
  5. Repeat until all subsets have been processed.
💡

Why Convert NFA to DFA?

DFAs are faster to simulate (O(n) time versus O(2^n) for NFAs) and are directly implementable in hardware and software. Most regex engines first convert the pattern to an NFA, then to a DFA for efficient matching.
⚠️

Exponential Blowup

A DFA may have up to 2n states for an NFA with n states. In the worst case, every subset of NFA states becomes a distinct DFA state. This is why DFA minimization is important — it reduces the state count.

Interview Questions

Q: What is the subset construction algorithm for NFA to DFA conversion?

A: The subset construction algorithm converts an NFA to an equivalent DFA by treating each set of NFA states as a single DFA state. For each DFA state (subset of NFA states) and each input symbol, we compute the set of NFA states reachable via that symbol (including ε-closure) to determine the next DFA state.

Q: Why might a DFA have exponentially more states than the original NFA?

A: A DFA state represents a subset of NFA states. With n NFA states, there are 2^n possible subsets, each of which could become a DFA state. In practice, many subsets are unreachable from the start state, so the actual DFA is usually much smaller than the theoretical maximum.

Q: What is ε-closure and why is it important in NFA to DFA conversion?

A: The ε-closure of a set of NFA states is the set of all states reachable from them using only ε-transitions (transitions on empty string). It is critical because ε-transitions allow an NFA to change state without consuming input; when converting to a DFA, we must account for all states reachable via ε at each step.