Past exam of the mathematics course of the University of Cambridge / 2026 / ii / Paper 2 / 4I / d / Solution

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.

Solved by gpt-5.6-sol high.