= Solution
A <context-free grammar> is an <ambiguous grammar> if some terminal <string> has two distinct <parse trees>, equivalently two distinct leftmost derivations. Different orders of expanding independent nonterminals do not by themselves constitute ambiguity.
The <context-free grammar> just given is \b[unambiguous]. It suffices to prove this for the reversed productions, because reversing a <parse tree> preserves whether two <parse trees> are distinct.
For $D$, the empty <string> forces the empty production. A nonempty <string> must use $D\to0D1D$. In any resulting nonnegative balanced path, the displayed one is the unique first return to zero. It therefore uniquely determines the two shorter substrings generated by $D$. <Mathematical induction> on length makes both smaller <parse trees> unique.
For $U$, the empty <string> again forces the empty production. A nonempty path with no return to zero must use $U\to0U$, since $0D1U$ always returns to zero. A path with a return must use $U\to0D1U$, since $0U$ stays positive after its first step. In the latter case, the first return uniquely determines the $D$ substring and the remaining $U$ substring. Applying <mathematical induction> to these shorter substrings proves uniqueness throughout. Hence
$$
\boxed{\text{The grammar in part (b)(i) is unambiguous}.}
$$
Back to article page
