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

A state $q$ is inaccessible when no word $w\in {\Sigma }^{\ast }$ has $\hat{\delta }(q_0,w)=q$.

Set $p\sim q$ when $\hat{\delta }(p,w)\in F⟺\hat{\delta }(q,w)\in F$ for every word $w$. Put ${\delta }^{\prime }([q],a)=[\delta (q,a)]$ and $F^{\prime }=\{[q]:q\in F\}$. If $p\sim q$, then testing continuations $aw$ shows $\delta (p,a)\sim \delta (q,a)$, so ${\delta }^{\prime }$ is well-defined.

The Myhill-Nerode theorem says this quotient is, up to isomorphism, the unique accessible DFA with the least possible number of states accepting the language.

Take states $0,\dots ,2n-1$, transition $j\mapsto j+1(\mathrm{mod}2n)$, initial state $0$, and make every even state accepting. Every state is reached by some $a^j$, and two states are equivalent exactly when they have the same parity. The quotient therefore has two states and accepts the even-length words.