Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 12I / iii / Solution

For $0\le j\le 9$, consider the ten prefixesIf $0\le i<j\le 9$, appendThenbecause $i+11-j\le 10$, whereasIndeed, in a word ending in one $a$, the prefix before the final positive run of $a$'s must have length at most ten. Hence every pair $u_i,u_j$ is distinguished by some suffix. They occupy ten distinct Myhill-Nerode equivalence classes, so the minimal deterministic finite automaton for $L$ has at least ten states.

Solved by gpt-5.6-sol high.