The Subset Construction

The Goal

Convert an NFA (or NFA-$\varepsilon$) $M$ to an equivalent DFA $\mathcal{P}(M)$ that recognises the same language.

The Construction

Input

NFA-$\varepsilon$ $M = (Q, \Sigma, \Delta, \tau, s, F)$

Output

DFA $\mathcal{P}(M) = (Q', \Sigma, \delta', s', F')$

States

$Q' = \mathcal{P}(Q) = \{S : S \subseteq Q\}$

Each DFA state is a set of NFA states.

Start State

$s' = E(s) = \{q' : s \xrightarrow{\varepsilon^*} q'\}$

The $\varepsilon$-closure of the NFA’s start state.

Accepting States

$F' = \{S \subseteq Q : S \cap F \neq \emptyset\}$

A DFA state is accepting if it contains at least one NFA accepting state.

Transition Function

For $S \subseteq Q$ and $a \in \Sigma$:

$\delta'(S, a) = \bigcup_{q \in S} \{q' : q \xrightarrow{a} q'' \xrightarrow{\varepsilon^*} q' \text{ for some } q''\}$

Equivalently: the set of all states reachable from $S$ on symbol $a$, followed by any number of $\varepsilon$-transitions.

Algorithm Summary

1. Start with $\varepsilon$-closure of $\{s\}$
2. For each reachable set $S$ and symbol $a$, compute $\delta'(S, a)$
3. Add newly discovered states to worklist
4. Repeat until no new states

Example

NFA

$M$: $Q = \{q_0, q_1, q_2\}$, $s = q_0$, $F = \{q_2\}$

Transitions:

• $q_0 \xrightarrow{a} q_0$, $q_0 \xrightarrow{a} q_1$
• $q_1 \xrightarrow{b} q_2$

DFA Construction

Start: $s' = E(q_0) = \{q_0\}$

Compute transitions:

DFA State	$a$	$b$
$\{q_0\}$	$\{q_0, q_1\}$	$\emptyset$
$\{q_0, q_1\}$	$\{q_0, q_1\}$	$\{q_2\}$
$\{q_2\}$	$\emptyset$	$\emptyset$
$\emptyset$	$\emptyset$	$\emptyset$

Accepting: $F' = \{\{q_2\}\}$ (states containing $q_2$)

Resulting DFA

Size

Worst Case

The DFA can have up to $2^{|Q|}$ states.

Typical Case

Many subsets may be unreachable, so the actual DFA is often smaller.

Exponential Blowup

Some NFAs require exponentially many DFA states. Example: language of strings where the $n$-th symbol from the end is $a$ requires $\Omega(2^n)$ DFA states but only $n+1$ NFA states.

Key Intuition

The DFA simulates “all possible computations” of the NFA simultaneously.

• DFA state $=$ set of NFA states that could be active
• Transition $=$ move all active states, take $\varepsilon$-closures
• Accepting $=$ any active state is an NFA accept state

---

Summary

• Subset construction: NFA state $\mapsto$ DFA state = set of NFA states
• DFA simulates all NFA computations in parallel
• Start state = $\varepsilon$-closure of NFA start
• Accept if intersection with $F$ is non-empty
• Worst case: exponential blowup in state count