Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2024/ii/paper-3/12j/b/solution

Let a deterministic automaton for have states. During the first input symbols of an accepted word of length at least , the run visits states, so two coincide. Write so that labels the nonempty loop between those visits and . Traversing that loop any number of times leaves the remainder of the accepting run unchanged, giving for every .

New to topics? Read the docs here!