Consider the grammar S → SbS | a. The string abababa has (A) two parse trees (B) two leftmost derivations (C) two rightmost derivations. Which is correct?

1. AAll (A), (B) and (C) are true
2. BOnly (B) is true
3. COnly (C) is true
4. DOnly (A) is true

Pick an option to check yourself, or open the answer below.

Show answer & explanation

Correct answer: A. All (A), (B) and (C) are true

Explanation

The grammar is ambiguous: abababa has several parse trees (it has four b's to split on — 5 trees in all). Each parse tree has its own leftmost and rightmost derivation, so (A), (B) and (C) all hold.