Consider the grammar S → SbS | a. Consider the following statements: The…

Concept — For any context-free grammar, the parse trees of a string, its leftmost derivations and its rightmost derivations stand in one-to-one correspondence. Expanding a parse tree leftmost-first yields exactly one leftmost derivation, expanding the same tree rightmost-first yields exactly one rightmost derivation, and every derivation rebuilds exactly the tree it came from. So for every string the three counts are equal, and a grammar is ambiguous precisely when some string admits more than one of them.

Application — In S → SbS | a each use of S → SbS contributes exactly one b and each use of S → a contributes exactly one a, so the generated language is a(ba)*. A parse tree for such a string is fixed by choosing which b sits at the root; that b splits the string into a left part and a right part, each again of the form a(ba)*.

1. Let T(k) be the number of parse trees of the string carrying k occurrences of b. Splitting at the root gives T(k) = T(0)T(k−1) + T(1)T(k−2) + … + T(k−1)T(0), the Catalan recurrence.

2. T(0) = 1 for the string a, and T(1) = 1 for the string aba.

3. T(2) = T(0)T(1) + T(1)T(0) = 1 + 1 = 2 for the string ababa.

4. T(3) = T(0)T(2) + T(1)T(1) + T(2)T(0) = 2 + 1 + 2 = 5.

5. abababa carries three b's and four a's, so it has T(3) = 5 distinct parse trees, and therefore 5 leftmost derivations and 5 rightmost derivations.

Two of those five leftmost derivations are set side by side below. The first grows the tree towards the right, the second grows it towards the left; the two sequences already differ at the second step, so they are genuinely distinct leftmost derivations belonging to two different parse trees.

The same two parse trees give two distinct rightmost derivations:

• Rightmost derivation 1: S ⇒ SbS ⇒ SbSbS ⇒ SbSbSbS ⇒ SbSbSba ⇒ SbSbaba ⇒ Sbababa ⇒ abababa

• Rightmost derivation 2: S ⇒ SbS ⇒ Sba ⇒ SbSba ⇒ Sbaba ⇒ SbSbaba ⇒ Sbababa ⇒ abababa

Cross-check — Because the three counts are always equal, no string under any grammar can make exactly one of the statements hold while the other two fail:

• “Only (A) is true” would need two parse trees but a single leftmost derivation; each of the two trees supplies its own leftmost derivation, so this cannot happen.

• “Only (B) is true” would need two leftmost derivations but a single parse tree; two distinct leftmost derivations rebuild two distinct parse trees, so this cannot happen either.

• “Only (C) is true” fails for the same reason on the rightmost side.

Result — abababa has five parse trees, five leftmost derivations and five rightmost derivations, so it certainly exhibits two of each — and exhibiting two distinct ones is exactly what these statements assert, the standard way of witnessing that S → SbS | a is ambiguous. The three statements stand or fall together, and all three hold, so the correct choice is “All (A), (B) and (C) are true”.

Note on the shorter string: ababa carries two b's, so T(2) = 2 gives it exactly two parse trees, exactly two leftmost derivations and exactly two rightmost derivations. A walkthrough on ababa therefore illustrates the same idea with the counts landing on exactly two; for abababa the counts rise to five while the conclusion is unchanged.

Note on the official key: the NTA final answer key for this paper recorded “Only (A) is true”. That reading cannot hold, because the one-to-one correspondence above forces two parse trees to be accompanied by two leftmost and two rightmost derivations. The standard published solutions therefore mark “All (A), (B) and (C) are true”.