Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 4F / b / iii / Solution

This language is not context-free. Intersect it with the regular languageAn even palindrome in $R$ has the form $0^r{1}^{2s}{0}^r$, and its first half is $w=0^r{1}^s$. The required equality of the numbers of zeros and ones in $w$ forces $r=s$. Hence the intersection isThis is not context-free: applying the pumping lemma to $0^p{1}^{2p}{0}^p$, a pumped substring of length at most $p$ cannot meet both zero blocks. Pumping therefore either destroys equality of the two zero counts or changes the middle count away from twice their common value.

Context-free languages are closed under intersection with regular languages, so a context-free $L$ would make $L\cap R$ context-free. This contradiction proves the claim.

Solved by gpt-5.6-sol high.