Let \(πΊ=(π,π,π,π)\) be a context-free grammar such that every one of itsβ¦
2016
LetΒ \(πΊ=(π,π,π,π)\)Β be a context-free grammar such that every one of its productions is of the formΒ \(π΄βπ\), withΒ \(|π|=π>1\).Β The derivation tree for any stringΒ \(πβπΏ(πΊ)\)Β has a height such that
- A.
\(h < \frac{(|W|-1)}{k-1}\) - B.
\(\log_{k} |W| \leq h\) - C.
\(\log_{k} |W| < h < \frac{(|W|-1)}{k-1}\) - D.
\(\log_{k} |W| \leq h \leq \frac{(|W|-1)}{k-1}\)
Attempted by 37 students.
Show answer & explanation
Correct answer: D
Claim: For any string W produced by the grammar, if the derivation tree has height h and |W| denotes the number of leaves (terminal symbols), then log_k |W| β€ h β€ (|W|-1)/(k-1).
Lower bound: Each internal node can have at most k children, so a tree of height h has at most k^h leaves. Therefore |W| β€ k^h, which implies h β₯ log_k |W|.
Upper bound: Every production replaces a nonterminal by exactly k symbols, so every internal node has exactly k children. In such a full k-ary tree with I internal nodes and L leaves we have L = (k-1)I + 1 (since total edges = kI and total nodes = I + L, giving I + L - 1 = kI). Solving gives I = (L-1)/(k-1). The height h cannot exceed the number of internal nodes along a root-to-leaf path, so h β€ I = (|W|-1)/(k-1).
Conclusion: Combining the two bounds yields log_k |W| β€ h β€ (|W|-1)/(k-1).
Remarks: The lower bound is achieved when the tree is perfectly balanced (all leaves at the same depth). The upper bound is achieved when internal nodes line up so that the number of internal nodes equals the height.