Consider the grammar G S→ SaS | b For a string “bababab”, the number of parse…
Consider the grammar G
S→ SaS | b For a string “bababab”, the number of parse tree that can be generated are ______
Answer: 5 — Answer: 5 parse trees. Explanation: 1) Count the number of b terminals in the string "bababab". There are 4 b's. 2) Key insight: Each application of the…
Attempted by 357 students.
Show answer & explanation
Correct answer: 5
Answer: 5 parse trees.
Explanation:
1) Count the number of b terminals in the string "bababab". There are 4 b's.
2) Key insight: Each application of the production S → S a S corresponds to an internal node of a full binary tree, and each terminal b corresponds to a leaf. A parse tree for a string with n leaves (b's) is a full binary tree with n leaves.
3) The number of distinct full binary trees with n leaves is the Catalan number C_{n-1}. For n = 4 leaves, we need C3.
Compute C3 using the formula Ck = (1/(k+1)) * binomial(2k, k).
C3 = (1/4) * binomial(6, 3) = (1/4) * 20 = 5.
Therefore, there are 5 distinct parse trees for the string "bababab". (The original image shows these five parse trees.)