Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as…
2007
Consider the CFG with { S, A, B } as the non-terminal alphabet, { a, b } as the terminal alphabet, S as the start symbol and the following set of production rules:
For the string aabbab, how many derivation trees are there?
- A.
1
- B.
2
- C.
3
- D.
4
Attempted by 10 students.
Show answer & explanation
Correct answer: B
S → aB
→ aaBB
→ aabB
→ aabbS
→ aabbaB
→ aabbab
S → aB
→ aaBB (till now, only 1 choice possible)
→ aabSB (last time we took B → b, now taking B → bS)
→ aabbAB
→ aabbaB
→ aabbab
So, totally 2 possible derivation trees.
Correct Answer: B