Past exam of the mathematics course of the University of Cambridge / 2018 / ii / Paper 2 / 4G (Automata and Formal Languages)

For a set $S\subseteq Q_E$, let $E(S)$ be its epsilon closure, and putThe subset construction with epsilon transitions gives the deterministic finite automatonUnreachable subsets may be deleted from $Q_D$ without changing the recognized language.

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.

A word $w$ is accepted by the Epsilon-NFA precisely whenBy part (b), this reached subset is exactly ${\hat{\delta }}_D(q_D,w)$, and by the definition of $F_D$ the intersection condition is equivalent to ${\hat{\delta }}_D(q_D,w)\in F_D$. Hence