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

Use the following context-free grammar, with start symbol $S$:The symbol $B$ generates the balanced members of the suffix-nonnegative binary language, while $S$ permits extra zeros. To prove the claim and prepare the ambiguity argument, reverse every generated string. The reversed productions areHere $U$ represents the reversals of the $S$ strings, and $D$ represents the reversals of the $B$ strings. A string belongs to the desired formal language precisely when its reversal has no string prefix with more ones than zeros. Associate a path with each reversed string, counting a zero as a step $+1$ and a one as a step $-1$.

The nonterminal $D$ generates exactly the paths that stay nonnegative and finish at zero. The production $0D1D$ consists of an initial up-step, a balanced path one level higher, a down-step to zero, and another balanced path. Conversely, any nonempty balanced nonnegative path has a first return to zero, and splitting there gives exactly this form. Mathematical induction on length proves the characterization.

The productions for $U$ generate nonnegative paths: $0U$ stays strictly above zero after its first step, while $0D1U$ first executes a balanced excursion and then another nonnegative path. Conversely, a nonempty nonnegative path starts with zero. If it never returns to height zero, removing that initial zero leaves a nonnegative path, giving $0U$. If it does return, split at its first return to obtain $0D1U$. These shorter components can be generated by mathematical induction. This proves that the original context-free grammar generates exactly the required formal language.

For instance, in the original context-free grammar,while $S\Rightarrow S1B0\Rightarrow S1B01B0{\Rightarrow }^{\ast }1010$. The string $110$ is excluded since its entire length is a string suffix having two ones and only one zero.

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