Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Calculus, linear algebra, discrete mathematics, logic and proof, and models of computation / 9 / b / ii / Solution

These strings are the even-length palindromes $u{u}^R$. Suppose this were a regular language, and let $p$ be its length from the pumping lemma for regular languages. The stringbelongs to the formal language, with $u=0^{p}1$. In any allowed decomposition $w=abc$, where $|ab|\le p$ and $|b|>0$, the pumped block is $b=0^k$ with $1\le k\le p$. Pumping it away givesThis is not a palindrome: its initial and final runs of zeros have different lengths. Hence it cannot have the form $u{u}^R$, contradicting the pumping lemma for regular languages. Therefore