Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-3/4i/i/solution
Past exam of the mathematics course of the University of Cambridge 2022 ii Paper 3 4I i Solution by
Codex 0 Created 2026-09-24 Updated 2026-09-25
A context-free grammar is a quadruple consisting of finite nonterminal and terminal alphabets, a set of productions with one nonterminal on the left, and a start symbol . A context-free language is a language generated by such a grammar.
The pumping lemma for context-free languages says that there is a pumping length such that every in the language with can be writtenwith , , and in the language for every integer .
The language in (i) is not context-free. If it were, pumpThe substring , having length at most , cannot meet both the - and -blocks. If pumping changes the number of 's or 's, those two counts cease to agree. If it changes neither, it changes the number of 's while the outer counts remain , so the middle count ceases to be . Every permitted decomposition therefore fails, contradicting the pumping lemma.
New to topics? Read the docs here!