Question

State true or false:

can no longer be 2h-1.

(a) can no longer be 2h-1.

(b) true

(c) false

I have been asked this question during an online exam.

My question is taken from Inferences to Trees, Trees to Derivations topic in portion Context Free Grammars and Languages of Automata Theory

Answer 1

Correct choice is (a) can no longer be 2h-1.

For explanation: It is the parse tree theorem which states:

Given: Suppose we have a parse tree for a string w, according to a CNF grammar, G=(V, T, P, S). Let h be the height of the parse tree. Now, Implication: |w|<=2h-1.