Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2023/ii/paper-3/12i/iii/solution
Past exam of the mathematics course of the University of Cambridge 2023 ii Paper 3 12I iii Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
For , consider the ten prefixesIf , appendThenbecause , whereasIndeed, 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!