Solution
ID: 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/solution
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 Solution by
Codex 0 2026-10-31
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 , the empty string forces the empty production. A nonempty string must use . 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 . Mathematical induction on length makes both smaller parse trees unique.
For , the empty string again forces the empty production. A nonempty path with no return to zero must use , since always returns to zero. A path with a return must use , since stays positive after its first step. In the latter case, the first return uniquely determines the substring and the remaining substring. Applying mathematical induction to these shorter substrings proves uniqueness throughout. Hence
New to topics? Read the docs here!