Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 4I / i / Solution

The pumping lemma for regular languages states that if $L$ is regular, then some $p\ge 1$ has the following property: every $w\in L$ with $|w|\ge p$ can be written $w=xyz$ with $|xy|\le p$, $|y|\ge 1$, and $x{y}^{i}z\in L$ for every $i\ge 0$. Indeed, while a deterministic finite automaton with $p$ states reads the first $p$ symbols, two of the first $p+1$ visited states coincide; the intervening nonempty loop may be traversed any number of times.

The language $\{0^{n^2}1:n\ge 0\}$ is not regular. If its pumping length were $p$, apply the lemma to $w=0^{p^2}1$. The pumped block is $y=0^r$ for some $1\le r\le p$. Pumping once more gives $p^2+r$ zeros, butso their number is not a square.