Solution
ID: 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/b/solution
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 b Solution by
Codex 0 2026-10-31
The assertion is false. Use the pumping lemma for regular languages: if is a regular language, there is such that every with admits a factorization with , , and for every integer .
Suppose the stated formal language were a regular language, and take . This string has twice as many zeros as ones, so it belongs to . In every allowed factorization, the first positions are all zeros, forcing with . Pumping down with producesIt still has ones but fewer than zeros, contradicting the pumping lemma for regular languages. Thus
New to topics? Read the docs here!