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

The subset construction theorem gives $\mathcal{L}(D)=\mathcal{L}(N)$. Removing inaccessible states does not alter any computation from the initial state, so

Every state of $D^{\prime }$ is accessible by construction. It remains to separate distinct subset states $S,T$ of $D^{\prime }$. Choose $q\in S△T$, and without loss of generality take $q\in S\setminus T$. By (Br2), some word $w$ has a witnessing sequence from $q$ to the unique final state $q_{\ast }$. Part (b)(iii) impliesso the state reached from $S$ on $w$ is accepting.

If the state reached from $T$ on $w$ were also accepting, there would be some $p\in T$ with a witnessing sequence labelled $w$ from $p$ to $q_{\ast }$. But $q$ has such a sequence too, and (Br3) says that its starting state is unique. Hence $p=q$, contradicting $q\notin T$. Thus $w$ distinguishes $S$ and $T$.

No two distinct states of $D^{\prime }$ are indistinguishable, and all are accessible. Therefore $D^{\prime }$ is irreducible and accepts $\mathcal{L}(N)$.

Solved by gpt-5.6-sol high.