Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → v, with |v| = k > 1. The derivation tree for any…
Let G = (V, T, S, P) be a context-free grammar such that every one of its productions is of the form A → v, with |v| = k > 1. The derivation tree for any string W ∈ L(G) has a height such that
Show answerHide answer
Correct answer: (D) logₖ |W| ≤ h ≤ (|W| – 1)/(K – 1)
Explanation
Each internal node of the derivation tree has exactly k children. The tree is shortest when it is complete, giving h ≥ logₖ |W|, and tallest when each level has only one internal node, giving h ≤ (|W| – 1)/(k – 1). So logₖ |W| ≤ h ≤ (|W| – 1)/(k – 1).