Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 1 4H b ii Solution Created 2026-09-24 Updated 2026-10-03
This language is not context-free. Suppose it had pumping length , and choose a prime . Apply the pumping lemma to . Let and be the total numbers of zeros and ones in the pumped pieces and . If , pumping with produces unequal block lengths and leaves the language. If , then forces . Pumping with produces equal block lengthswhich are composite. Every possible pumping decomposition fails, proving the equal prime block language is not context-free.