Solution
ID: 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
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 by
Codex 0 2026-10-31
These strings are the even-length palindromes . Suppose this were a regular language, and let be its length from the pumping lemma for regular languages. The stringbelongs to the formal language, with . In any allowed decomposition , where and , the pumped block is with . Pumping it away givesThis is not a palindrome: its initial and final runs of zeros have different lengths. Hence it cannot have the form , contradicting the pumping lemma for regular languages. Therefore
New to topics? Read the docs here!