= Solution
Let $\widehat\delta_E(q_0,w)$ mean all states reachable after reading $w$, allowing arbitrary epsilon transitions before, between, and after its symbols. We prove by <mathematical induction> on $|w|$ that
$$
\widehat\delta_E(q_0,w)=\widehat\delta_D(q_D,w).
$$
For $w=\epsilon$, both sides equal $E(\{q_0\})=q_D$. Suppose the claim holds for $w$, and append $a\in\Sigma$. By the definitions of the extended transition functions and the subset construction,
$$
\widehat\delta_E(q_0,wa)
=E\bigl(\delta_E(\widehat\delta_E(q_0,w),a)\bigr)
=\delta_D(\widehat\delta_D(q_D,w),a)
=\widehat\delta_D(q_D,wa).
$$
This completes the induction.
Back to article page
