Consider the grammer S→SbS∣a. Consider the following statements: The string…
2022
Consider the grammer S→SbS∣a. Consider the following statements:
The string abababa has
(A) two parse trees
(B) two left most derivations
(C) two right most derivations
Which of the following is correct ?
- A.
All (A). (B) and [(𝐶)] are true,
- B.
Only (B) is true
- C.
Only (C) is true
- D.
Only (A) is true
Attempted by 113 students.
Show answer & explanation
Correct answer: A
Answer: None of the three statements is true.
Explanation:
Count the terminals in the string abababa: there are four 'a' symbols and three 'b' symbols.
Each derivation using the rule S → S b S builds an internal node (a 'b') that joins two subtrees; the leaves of the full binary tree are precisely the 'a' terminals. Therefore parse trees for this grammar correspond to full binary tree shapes with one leaf per 'a'.
With 4 leaves, the number of distinct full binary tree shapes is the Catalan number C3 = 5.
Each distinct parse tree gives a unique leftmost derivation and a unique rightmost derivation, so there are five leftmost derivations and five rightmost derivations as well.
Therefore, the statements claiming there are exactly two parse trees, two leftmost derivations, or two rightmost derivations are all false.
A video solution is available for this question — log in and enroll to watch it.