Q2Theory of Computation

Given NFA $N=(Q_N,\Sigma ,{\delta }_N,q_0,F_N)$, construct DFA $M=(Q_D,\Sigma ,{\delta }_D,d_0,F_D)$ as follows: (1) The start state $d_0=ϵ\text{-closure}(\{q_0\})$, the set of NFA states reachable from $q_0$ using only $ϵ$-transitions. (2) For each DFA state $S$ (a subset of $Q_N$) and each input symbol $a$, compute ${\delta }_D(S,a)=ϵ\text{-closure}\left({\bigcup }_{q\in S}{\delta }_N(q,a)\right)$ — move on $a$ from every NFA state in $S$, then take the $ϵ$-closure of the result. (3) Repeat step 2 for every newly discovered subset until no new subsets appear (this is done lazily, only constructing reachable subsets, to avoid the full $2^{|Q_N|}$ blow-up when unnecessary). (4) A DFA state $S\in F_D$ if and only if $S\cap F_N\ne \varnothing$, i.e., the subset contains at least one NFA accepting state.

Consider an NFA over $\{0,1\}$ with states $\{A,B,C\}$, start state $A$, final state $\{C\}$, and transitions $\delta (A,0)=\{A,B\}$, $\delta (A,1)=\{A\}$, $\delta (B,1)=\{C\}$ (no $ϵ$-transitions in this example, so $ϵ$-closure of any set is itself). This NFA accepts strings ending in '01'. Apply subset construction: start state $d_0=\{A\}$. From $\{A\}$: on 0, $\delta (A,0)=\{A,B\}$, giving new state $\{A,B\}$; on 1, $\delta (A,1)=\{A\}$, staying at $\{A\}$. From $\{A,B\}$: on 0, $\delta (A,0)\cup \delta (B,0)=\{A,B\}\cup \varnothing =\{A,B\}$ (self-loop); on 1, $\delta (A,1)\cup \delta (B,1)=\{A\}\cup \{C\}=\{A,C\}$, a new state. From $\{A,C\}$: on 0, $\delta (A,0)\cup \delta (C,0)=\{A,B\}\cup \varnothing =\{A,B\}$ (already seen); on 1, $\delta (A,1)\cup \delta (C,1)=\{A\}\cup \varnothing =\{A\}$ (already seen). No further new subsets arise, so the reachable DFA states are $\{A\},\{A,B\},\{A,C\}$, with $\{A,C\}$ the only final state (it contains $C$).

Renaming $\{A\}=p_0$ (start), $\{A,B\}=p_1$, $\{A,C\}=p_2$ (final), the DFA has transitions $\delta (p_0,0)=p_1$, $\delta (p_0,1)=p_0$, $\delta (p_1,0)=p_1$, $\delta (p_1,1)=p_2$, $\delta (p_2,0)=p_1$, $\delta (p_2,1)=p_0$. Correctness of subset construction follows by induction on input length: the invariant 'after reading prefix $w$, the DFA is in state ${\hat{\delta }}_D(d_0,w)=\{q\in Q_N\mid q\text{ is reachable from }{q}_0\text{ in }N\text{ via }w\}$' holds at the base case (empty string, by definition of $d_0$) and is preserved by the transition definition at each step, so the DFA is in an accepting state after $w$ exactly when some NFA computation path on $w$ ends in an NFA-accepting state, meaning $L(M)=L(N)$.