Past exam of the year 1 of the computer science course of the University of Oxford / 2003 / Calculus, probability, linear algebra, discrete mathematics, logic and proof, and models of computation / 10 / b / ii

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 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\to 0D1D$. 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\to 0U$, since $0D1U$ always returns to zero. A path with a return must use $U\to 0D1U$, 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