= Solution
For a <deterministic finite automaton> the <extended transition function of a deterministic finite automaton> is recursively
$$
\widehat\delta(q,\epsilon)=q,
\qquad
\widehat\delta(q,wa)=\delta(\widehat\delta(q,w),a).
$$
The accepted language is
$$
L(D)=\{w\in\Sigma^*: \widehat\delta(q_0,w)\in F\}.
$$
For a <nondeterministic finite automaton>, $\widehat\delta(q,w)$ is the set of all states reachable from $q$ while reading $w$; recursively,
$$
\widehat\delta(q,\epsilon)=\{q\},
\qquad
\widehat\delta(q,wa)=\bigcup_{r\in\widehat\delta(q,w)}\delta(r,a).
$$
Thus
$$
L(N)=\{w\in\Sigma^*: \widehat\delta(q_0,w)\cap F\ne\varnothing\}.
$$
The <powerset construction> has state set $\mathcal P(Q)$, initial state $\{q_0\}$, transition
$$
\overline\delta(S,a)=\bigcup_{q\in S}\delta(q,a),
$$
and accepting states $\{S\subseteq Q:S\cap F\ne\varnothing\}$. Induction on $|w|$ gives
$$
\widehat{\overline\delta}(\{q_0\},w)=\widehat\delta(q_0,w),
$$
so the two automata accept exactly the same language. If $|Q|=m$ and $F$ has one state, exactly $2^{m-1}$ of the $2^m$ subset states contain it and are accepting, including states that may be unreachable.
Back to article page
