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 $L$ is a regular language, there is $p\ge 1$ such that every $w\in L$ with $|w|\ge p$ admits a factorization $w=xyz$ with $|xy|\le p$, $|y|\ge 1$, and $x{y}^{k}z\in L$ for every integer $k\ge 0$.

Suppose the stated formal language were a regular language, and take $w=0^{2p}{1}^p$. This string has twice as many zeros as ones, so it belongs to $L$. In every allowed factorization, the first $p$ positions are all zeros, forcing $y=0^d$ with $1\le d\le p$. Pumping down with $k=0$ producesIt still has $p$ ones but fewer than $2p$ zeros, contradicting the pumping lemma for regular languages. Thus