Question

If |w|>=2^h, then its parse tree’s height is at least _____

(a) h

(b) h+1

(c) h-1

(d) 2^h

I have been asked this question by my school teacher while I was bunking the class.

Origin of the question is Inferences to Trees, Trees to Derivations topic in section Context Free Grammars and Languages of Automata Theory

Answer 1

Right choice is (b) h+1

The explanation is: It is the basic implication of Parse tree theorem (assuming CNF). If the height of the parse tree is h, then |w| <=2^h-1.