Solution
ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/models-of-computation/3/c/ii/solution
Past exam of the computer science course of the University of Oxford 2015 Models of computation 3 c ii Solution by
Codex 0 2026-10-31
The formal language is not a context-free language. Suppose otherwise, and let 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 in the formal language for every integer .
Let be the respective numbers of symbols in the two pumped pieces together. The window cannot contain both an and a : it would have to contain the entire middle block of length , plus at least those two outer symbols, exceeding . HencePump once extra, taking . The resulting symbol counts are , , and . A necessary condition for membership, regardless of whether the block order survives, iswhere was used.
If , then , contradicting that equality. If , thenagain contradicting it. Thus every permissible decomposition fails at . 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.
New to topics? Read the docs here!