Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 3 / 12F / b

Define the extended transition recursively byThe automaton accepts $w$ precisely when

The subset construction produceswhereEach deterministic state records all nondeterministic states reachable after the word read so far. This construction gives $\mathcal{L}(D)=\mathcal{L}(N)$.

We induct on the length of $w$. For $w=\epsilon$, the extended transition set is $\{q\}$, and the sole witnessing sequence is $(q)$, so the claim holds.

Write a nonempty word as $w=va$. By the recursive definition,if and only if there is some $p\in \hat{\Delta }(q,v)$ with $q^{\prime }\in \Delta (p,a)$. By the induction hypothesis, the first condition on $p$ is equivalent to a witnessing sequence for $v$ from $q$ to $p$. Appending $q^{\prime }$ gives a witnessing sequence for $va$. Conversely, deleting the last state of any witnessing sequence for $va$ gives just such a state $p$ and sequence for $v$. This proves both implications.