Question

State true or false:

can no longer be 2h-1.

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

(b) true

(c) false

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.