Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 3 / 12J / b / Solution

Let a deterministic automaton for $L$ have $p$ states. During the first $p$ input symbols of an accepted word $w$ of length at least $p$, the run visits $p+1$ states, so two coincide. Write $w=xyz$ so that $y$ labels the nonempty loop between those visits and $|xy|\le p$. Traversing that loop any number of times leaves the remainder of the accepting run unchanged, giving $x{y}^{i}z\in L$ for every $i\ge 0$.

Solved by gpt-5.6-sol high.