Let \(πΊ = (π,π,π,π)\) be a context-free grammer such that every one ofβ¦
2017
LetΒ \(πΊ = (π,π,π,π)\)Β be a context-free grammer such that every one of its productions is of the formΒ \(π΄ β π£,\) withΒ \(β£π£β£ = πΎ > 1\). The derivation tree for anyΒ \(πβπΏ(πΊ)\)Β has a heightΒ \(β\)Β such thatΒ
- A.
\(\log_{K} \mid W \mid \leq h\leq \log_{K} \left (\frac{ \mid W \mid-1}{K-1} \right ) \\\) - B.
\(\log_{K} \mid W \mid \leq h \leq \log_{K} \left ( K \mid W \mid \right) \\\) - C.
\(\log_{K} \mid W \mid \leq h \leq K \log_{K} \mid W \mid \\\) - D.
\(\log_{K}|W \mid \leq h \leq \left (\frac{ \mid W \mid β 1}{K-1} \right)\)
Attempted by 11 students.
Show answer & explanation
Correct answer: D
Correct inequality: log_K |W| β€ h β€ (|W|-1)/(K-1)
Reason:
Let I be the number of internal (variable) nodes in the derivation tree. Each internal node has K children, so the number of leaves (terminals) |W| satisfies |W| = I*(K-1) + 1.
Lower bound: For a tree of height h the maximum possible number of leaves is that of a full K-ary tree, namely K^h. Thus |W| β€ K^h, which implies h β₯ log_K |W|.
Upper bound: For fixed |W| the height is maximized when the tree is as unbalanced as possible (a chain of internal nodes). In that case each internal node contributes exactly (K-1) leaves, so I = h and |W| = h*(K-1) + 1. Solving gives h = (|W|-1)/(K-1), so h β€ (|W|-1)/(K-1).
Combining these bounds yields the stated inequality: log_K |W| β€ h β€ (|W|-1)/(K-1).