Past exam of the mathematics course of the University of Cambridge / 2025 / ii / Paper 2 / 4F (Automata & Formal Languages)

A language $L$ satisfies the context-free pumping lemma if there is an integer $p\ge 1$ such that every $z\in L$ with $|z|\ge p$ has a decompositionwithandEvery context-free language has this property, although the property by itself is not sufficient for context-freeness.

This language is not context-free. If $p$ were a pumping length, apply the lemma toBecause $|vwx|\le p$, the pumped region meets at most two adjacent blocks and cannot meet both zero blocks. Pumping with $i=0$ or $i=2$ changes at least one symbol count. If it changes either zero block, that block no longer agrees with the untouched zero block; if it changes only the middle block, the number of ones no longer agrees with the two zero counts. In every case the pumped word leaves the language, contradicting the lemma.

The language is context-free. A grammar with start symbol $S$ isEvery derivation adds matching symbols to the two ends and starts with a matching central pair, so it produces exactly the nonempty even palindromes $w{w}^R$.

This language is not context-free. Intersect it with the regular languageAn even palindrome in $R$ has the form $0^r{1}^{2s}{0}^r$, and its first half is $w=0^r{1}^s$. The required equality of the numbers of zeros and ones in $w$ forces $r=s$. Hence the intersection isThis is not context-free: applying the pumping lemma to $0^p{1}^{2p}{0}^p$, a pumped substring of length at most $p$ 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 $L$ would make $L\cap R$ context-free. This contradiction proves the claim.

This language is context-free. LetThe nonterminal $T$ produces exactly $1^m{0}^m$ with $m>0$. The base production for $S$ supplies one leading and one trailing zero, and each recursive production supplies one more of each. Thus $S$ produces exactly