Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/ii/paper-3/12i/iii/solution

For , consider the ten prefixes
If , append
Then
because , whereas
Indeed, in a word ending in one , the prefix before the final positive run of 's must have length at most ten. Hence every pair is distinguished by some suffix. They occupy ten distinct Myhill-Nerode equivalence classes, so the minimal deterministic finite automaton for has at least ten states.

New to topics? Read the docs here!