= Solution
One <parse tree> can be recorded unambiguously by the nested expression
$$
S\bigl(
A(A(a),B(b)),
C(B(b),A(A(A(a),B(b)),B(B(b),A(a))))
\bigr).
$$
Every internal node uses one of the given productions, and the leaves read from left to right are
$$
a,b,b,a,b,b,a.
$$
Equivalently, the corresponding leftmost <grammar derivation> is
$$
\begin{aligned}
S&\Rightarrow AC\Rightarrow ABC\Rightarrow aBC\Rightarrow abC
\Rightarrow abBA\Rightarrow abbA\\
&\Rightarrow abbAB\Rightarrow abbABB\Rightarrow abbaBB
\Rightarrow abbabB\Rightarrow abbabBA\\
&\Rightarrow abbabbA\Rightarrow\boxed{abbabba}.
\end{aligned}
$$
\b[Hence the required word is generated by the grammar.]
Back to article page
