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

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 produces
It still has ones but fewer than zeros, contradicting the pumping lemma for regular languages. Thus

New to topics? Read the docs here!