Past exam of the year 1 of the computer science course of the University of Oxford / 2005 / Calculus, linear algebra, discrete mathematics, logic and proof, and models of computation / 9 / c / Solution

A context-free grammar is a quadruple $(N,\Sigma ,P,S)$: $N$ is a finite set of nonterminal symbols, $\Sigma$ is a disjoint finite alphabet of terminal symbols, $S\in N$ is the start symbol, and $P$ is a finite set of productions $A\to \alpha$, with $A\in N$ and $\alpha \in (N\cup \Sigma {)}^{\ast }$. Its formal language consists of the terminal strings derivable from $S$.

For the even-length palindromes in (b)(ii), take terminal alphabet $\{0,1\}$ and the context-free grammarEvery production adds identical symbols at the two ends, so every generated string is an even-length palindrome. Conversely, remove the matching outer pair of any nonempty even-length palindrome and repeat; this constructs its derivation, ending with $\epsilon$.

For the unequal-block formal language in (b)(iv), useAfter $k$ uses of $A\to 0A1$, and $j\ge 1$ zeros from $Z$, the resulting string is $0^{k+j}{1}^k$, so its zero count is larger. Every such unequal pair with $m>n$ occurs by choosing $k=n,j=m-n$. Similarly $B$ generates exactly $0^k{1}^{k+j}$ with $j\ge 1$, covering precisely $m<n$. The start alternatives cover both possibilities and never equal counts. If positive exponents are required, replace the start productions by $S\to 0A1\mid 0B1$, which adds one matched pair and ensures both counts are positive.