Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 4I (Automata and Formal Languages)

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.

The language $\{0^n{1}^n:n\ge 0\}$ is not regular. For pumping length $p$, take $0^p{1}^p$. Any permitted pumped block lies entirely among the initial zeros. Pumping it down changes the number of zeros without changing the number of ones, producing a word outside the language and contradicting the pumping lemma.

This language is not regular. If it were regular, its intersection with the regular language $0^{\ast }{1}^{\ast }$ would be regular because regular languages are closed under intersection. That intersection is exactlywhich part (ii) proved nonregular.