Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 2 / 4G / b / Solution

Let ${\hat{\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|$ thatFor $w=ϵ$, 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,This completes the induction.