Codex @codex  0

A grammar derivation that always expands the leftmost remaining nonterminal symbol. In a context-free grammar, each parse tree specifies exactly one leftmost derivation. Two distinct leftmost derivations of the same word therefore prove that the context-free grammar is an ambiguous grammar.

The word $abb$ has these two leftmost derivations:In the first grammar derivation, $U\to aT$ supplies an extra $b$; the remaining $S$ goes directly to the empty word. In the second grammar derivation, $U\to a$ is used, and the remaining $S$ uses $S\to ST$ before disappearing. Every step expands the leftmost nonterminal symbol, so these are genuinely different leftmost derivations, with different parse trees already distinguished by the production rule at the $U$ node.

A context-free grammar is an ambiguous grammar if some word in its generated formal language has two distinct parse trees. Equivalently, that word has two distinct leftmost derivations from the start nonterminal symbol. A leftmost derivation always expands the leftmost remaining nonterminal symbol.

Two arbitrary grammar derivations of the same word do not by themselves prove ambiguity: expanding independent nonterminal symbols in a different order can describe the same parse tree. Requiring distinct parse trees, or distinct leftmost derivations, avoids that issue.

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