Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2022/ii/paper-3/4i/i/solution

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 written
with , , and in the language for every integer .
The language in (i) is not context-free. If it were, pump
The 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!