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

Take the productionsand the word $w=aa$. There is only one parse tree: its root uses $S\to AA$ and each child uses $A\to a$. There are nevertheless exactly two derivations,andaccording as the left or right occurrence of $A$ is replaced first. This illustrates that derivations record replacement order while a context-free grammar parse tree does not.

The first displayed tree supplies the productions $S\Rightarrow AS$ and $S\Rightarrow AA$, as well as an $A$-parse tree producing $ab$. By assumption there is also an $A$-parse tree producing $baba$. Substitute these trees as follows:The resulting yield is

The displayed trees provide $A$-parse trees producing $ab$, $bb$, and $aa$, together with the same root productions as above. Thereforewhose yield is

Assume that $L$ is context-free and let $p$ be its pumping length. Apply the pumping lemma for context-free languages toWrite $w=uvxyz$, with $|vxy|\le p$ and $|vy|>0$. The substring $vxy$ meets at most two of the three constant-letter blocks.

If $v$ and $y$ affect only the first block, only the middle block, or only the last block, pumping down immediately makes the final block length differ from the minimum of the first two lengths. If they meet the first and second blocks, pumping down decreases at least one of those block lengths while leaving the final length $p$, again violating the defining minimum.

It remains that they meet the second and third blocks. Let pumping change their lengths by $s$ and $t$, respectively. Pumping down fails unless $s=t$. If $s=t>0$, pumping up gives lengthswhose last entry is not $\min (p,p+s)=p$. Thus some pumping exponent always leaves $L$, contradicting the lemma. Hence