Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 9 / c

The assertion is false. Suppose the formal language $L=\{ww:w\in \{0,1{\}}^{\ast }\}$ were a regular language, and let $p$ be its constant from the pumping lemma for regular languages. ConsiderIn every decomposition $t=xyz$ with $|xy|\le p$ and $|y|\ge 1$, the pumped factor is $y=0^d$ with $1\le d\le p$. Pumping down givesThis string has exactly two ones and ends in a one. If it were $vv$, each copy of $v$ would contain exactly one one, and each copy would end in a one. The first copy would consequently be $0^{p-d}1$, while the second would be $0^{p}1$. They have different lengths because $d>0$, so they cannot be equal. This contradiction to the pumping lemma for regular languages proves