Past exam of the computer science course of the University of Oxford / 2015 / Models of computation / 2 / b / iv / Solution

Every generated word satisfieswhere ${\#}_a,{\#}_b$ count occurrences of the indicated terminal symbols. To see this, follow the unique chain of $S$ occurrences in a parse tree. Each use of $S\to UST$ introduces one $a$ from $U$, at least one $b$ from its rightmost $T$, and possibly one further $b$ from $U\to aT$. Each use of $S\to ST$ adds one $b$ and no $a$. The terminating $S\to \epsilon$ contributes neither. Hence no generated word has more $a$ symbols than $b$ symbols.

Also, for every $n\ge 0$, the word $a^n{b}^n$ is generated: apply $S\to UST$ exactly $n$ times, choose $U\to a$ each time, then use $S\to \epsilon$ and all remaining $T\to b$.

Suppose $L(G)$ were a regular language, and let $p\ge 1$ be a pumping length from the pumping lemma for regular languages. Apply it to $w=a^p{b}^p$. Every allowed decomposition $w=xyz$ with $|xy|\le p$ and $|y|>0$ has $y=a^r$ for some $r\ge 1$. Pumping twice giveswhich violates the proved counting inequality and hence is not generated. This contradicts the pumping lemma for regular languages. Therefore $L(G)$ is not a regular language. Ambiguity was not used: the obstruction is the unbounded constraint on symbol counts.