title: "Subset Construction"

Subset Construction

Definition. The subset construction turns an NFA $N = (Q, \Sigma, \delta, q_0, F)$ into a DFA recognizing the same language, by taking the DFA's states to be sets of $N$'s states: the start state is $\{q_0\}$, the transition is $\delta_D(S, a) = \bigcup_{q \in S} \delta(q, a)$, and a set accepts exactly when it meets $F$.

It is the parallel reading of nondeterminism written down: the set is exactly the collection of states $N$ could be in after reading the input so far, which is proved by induction on the input length. The DFA has up to $2^{|Q|}$ states, and that bound is met in the worst case, so the construction proves the two models equally powerful while showing determinism can cost exponentially more states. Introduced in Lecture 3.