Solution

ID: past-exam-of-the-computer-science-course-of-the-university-of-oxford/2015/models-of-computation/2/b/iv/solution

Every generated word satisfies
where count occurrences of the indicated terminal symbols. To see this, follow the unique chain of occurrences in a parse tree. Each use of introduces one from , at least one from its rightmost , and possibly one further from . Each use of adds one and no . The terminating contributes neither. Hence no generated word has more symbols than symbols.
Also, for every , the word is generated: apply exactly times, choose each time, then use and all remaining .
Suppose were a regular language, and let be a pumping length from the pumping lemma for regular languages. Apply it to . Every allowed decomposition with and has for some . Pumping twice gives
which violates the proved counting inequality and hence is not generated. This contradicts the pumping lemma for regular languages. Therefore is not a regular language. Ambiguity was not used: the obstruction is the unbounded constraint on symbol counts.

New to topics? Read the docs here!