Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 3 / c

The formal language is a context-free language. A context-free grammar with start nonterminal symbol $S$ isThe production rule for $A$ nests one $a$ on the left and one $b$ on the right on each recursive use, so $A$ generates exactly $a^m{b}^m$ for $m\ge 0$. Similarly, $B$ generates exactly $b^n{c}^n$ for $n\ge 0$. The start production rule concatenates these words, yieldingConversely, every choice of nonnegative integers $m,n$ is achieved by using the recursive production rules exactly $m,n$ times before their epsilon productions. Hence this context-free grammar generates precisely the required formal language, including all cases where either count is zero.

The formal language is not a context-free language. Suppose otherwise, and let $p\ge 1$ be a pumping length from the pumping lemma for context-free languages. ChooseThis word belongs to the formal language, since its middle exponent is the product of the two outer exponents. The pumping lemma for context-free languages would givewith $u{v}^{i}x{y}^{i}z$ in the formal language for every integer $i\ge 0$.

Let $\alpha ,\beta ,\gamma$ be the respective numbers of $a,b,c$ symbols in the two pumped pieces $v,y$ together. The window $vxy$ cannot contain both an $a$ and a $c$: it would have to contain the entire middle block of length $p^2$, plus at least those two outer symbols, exceeding $p$. HencePump once extra, taking $i=2$. The resulting symbol counts are $p+\alpha$, $p^2+\beta$, and $p+\gamma$. A necessary condition for membership, regardless of whether the block order survives, iswhere $\alpha \gamma =0$ was used.

If $\alpha +\gamma =0$, then $\beta >0$, contradicting that equality. If $\alpha +\gamma \ge 1$, thenagain contradicting it. Thus every permissible decomposition fails at $i=2$. This contradicts the pumping lemma for context-free languages and proves the claim. The obstruction is the multiplicative block-count language: a bounded local change cannot preserve the product constraint.