Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 3 / 4F / i / Solution

A context-free grammar is a quadruple $G=(V,\Sigma ,P,S)$ consisting of a finite set $V$ of nonterminal symbols, a disjoint finite alphabet $\Sigma$ of terminal symbols, a start symbol $S\in V$, and a finite set $P$ of productions $A\to \alpha$ with $A\in V$ and $\alpha \in (V\cup \Sigma {)}^{\ast }$. A sentence is a terminal word over an alphabet $w\in {\Sigma }^{\ast }$ with $S{\Rightarrow }^{\ast }w$, and the generated formal language is $\mathcal{L}(G)=\{w\in {\Sigma }^{\ast }:S{\Rightarrow }^{\ast }w\}$.

The first language is context-free. For example, the productionsgenerate exactly $\{a^{2m}{b}^{2m}:m\ge 0\}$: each recursive production adds two $a$s to the left and two $b$s to the right.