Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2025/ii/paper-2/4f/b/iii/solution
Past exam of the mathematics course of the University of Cambridge 2025 ii Paper 2 4F b iii Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
This language is not context-free. Intersect it with the regular languageAn even palindrome in has the form , and its first half is . The required equality of the numbers of zeros and ones in forces . Hence the intersection isThis is not context-free: applying the pumping lemma to , a pumped substring of length at most 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 would make context-free. This contradiction proves the claim.
New to topics? Read the docs here!