= Solution
Every generated <word> satisfies
$$
\#_b(w)\geq\#_a(w),
$$
where $\#_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\varepsilon$ contributes neither. Hence no generated <word> has more $a$ symbols than $b$ symbols.
Also, for every $n\geq0$, the <word> $a^nb^n$ is generated: apply $S\to UST$ exactly $n$ times, choose $U\to a$ each time, then use $S\to\varepsilon$ and all remaining $T\to b$.
Suppose $L(G)$ were a <regular language>, and let $p\geq1$ be a <pumping length> from the <pumping lemma for regular languages>. Apply it to $w=a^pb^p$. Every allowed decomposition $w=xyz$ with $|xy|\leq p$ and $|y|>0$ has $y=a^r$ for some $r\geq1$. Pumping twice gives
$$
xy^2z=a^{p+r}b^p,
$$
which violates the proved counting inequality and hence is not generated. This contradicts the <pumping lemma for regular languages>. \b[Therefore $L(G)$ is not a <regular language>.] Ambiguity was not used: the obstruction is the unbounded constraint on symbol counts.
$$
\boxed{L(G)\text{ is not regular}.}
$$
Back to article page
