Project Forge(Same CFG as before: S→aB|bA, B→b|bS|aBB, A→a|aS|bAA.) For the correct answer string to the previous question ('aabbab'), how many derivation trees are there?
- A1
- 2
- C3
- D4
Explanation
S must use S→aB (only option starting with 'a'), and the outer B must use B→aBB (only option starting with 'a', matching the remaining 'abbab'), needing the two child B's to jointly derive 'bbab'. Checking all ways to split 'bbab' into two B-derivable halves: (B₁='b', B₂='bab') works, and (B₁='bba', B₂='b') also works (B⇒bS⇒b(bA)⇒b(b(a))='bba'). No other split works. Each of these two splits has a uniquely-forced sub-derivation, giving exactly 2 distinct derivation trees.
Source: GATE CS 2007 (2007)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.