Past exam of the mathematics course of the University of Cambridge / 2019 / ii / Paper 1 / 4H (Automata and Formal Languages)

The pumping lemma for context-free languages states that for every context-free language $L$ there is a pumping length $p$ such that every $w\in L$ with $|w|\ge p$ can be writtenwith

This language is context-free. It is the language of even-length palindromes over $\{a,b\}$, generated by the context-free grammarEvery derivation adds matching outer symbols, and removing the matching first and last symbols gives the converse induction.

This language is not context-free. Suppose it had pumping length $N$, and choose a prime $p>N$. Apply the pumping lemma to $w=0^p{1}^p$. Let $\alpha$ and $\beta$ be the total numbers of zeros and ones in the pumped pieces $v$ and $y$. If $\alpha \ne \beta$, pumping with $i=0$ produces unequal block lengths and leaves the language. If $\alpha =\beta$, then $|vy|>0$ forces $\alpha =\beta =d>0$. Pumping with $i=p+1$ produces equal block lengthswhich are composite. Every possible pumping decomposition fails, proving the equal prime block language is not context-free.

The equations $3m=4l$ and $2n=5k$ are equivalent tofor nonnegative integers $r,s$. Hence the language iswhich is the nested two-pair count language generated byIt is therefore context-free.

Take context-free grammars $G_L,G_M$ for $L,M$ and rename their nonterminals so that they are disjoint. If their start symbols are $S_L,S_M$, add a new start symbol $S$ and the productionAll productions remain context-free. A derivation from $S$ produces a word from $L$ followed by a word from $M$, and every such concatenation has a derivation. Thus the new grammar generates $LM$, proving closure of context-free languages under concatenation.