Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/models-of-computation/3/c/ii/solution

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. Choose
This 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 give
with 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 . Hence
Pump once extra, taking . The resulting symbol counts are , , and . A necessary condition for membership, regardless of whether the block order survives, is
where was used.
If , then , contradicting that equality. If , then
again 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!