Subset Construction: NFA to DFA Conversion
You'll learn the systematic algorithm that transforms any NFA into an equivalent DFA by treating sets of NFA states as single DFA states.
The Core Idea
An NFA can be in multiple states simultaneously, but a DFA must be in exactly one state at a time. The subset construction algorithm resolves this by creating a DFA where each state represents a set of NFA states the original machine could be in.
Think of it like tracking possibilities: if an NFA could be in state {q₁, q₂, q₃} after reading "ab", the DFA has a single state representing that entire set. The DFA's states are the power set of the NFA's states—though in practice, you only build the reachable ones.
The Algorithm
-
Start state: Compute the epsilon-closure of the NFA's start state (all states reachable via ε-transitions). This set becomes the DFA's start state.
-
Transition function: For each DFA state S (a set of NFA states) and each alphabet symbol a:
- Find all NFA states reachable from any state in S on input a
- Take the epsilon-closure of that result
- This new set becomes the target DFA state
-
Accepting states: Any DFA state containing at least one NFA accepting state becomes an accepting state.
-
Repeat: Continue until no new sets appear.
Example Intuition
If your NFA has 4 states, the resulting DFA could theoretically have 2⁴ = 16 states (one for each subset). In practice, most subsets are unreachable, so you only construct what's needed.
Key Takeaway: Subset construction converts NFAs to DFAs by tracking all possible NFA states as single DFA states, proving that every language recognizable by an NFA is also recognizable by a DFA.