Q53,paper 3,D 12. If the parse tree of a word w generated by a Chomsky normal form grammar has no path of length greater than i, then the word w is of length

(A) no greater than 2ⁱ⁺¹

(B) no greater than 2ⁱ

(C) no greater than 2^i–1

(D) no greater than i.

Answer ©

Chomsky normal forms.

A->BC.

Where B,C are variables.

Or

A->a.(terminal)

Where as Greibach NF

A->aV1V2—Vk  where k>=0.

A is a terminal and Vi is a variable.

Let the following Chomsky grammar.

A->BC.

B->BC.

C->AC

A->AB.

A->a

B->b

C->c..

While making a parse tree, it is observed that.

When path is of length 1. It has the  form like A->a.   its length of word is 1.

When path  is of length 2. It has the form A-> AB->ab. Or Or A->BC->bc. Its length of word is 2.

When path is of length 3. It has the form A->AB->ABBC->abbc its length is of 4.

So it is generalized as path of length i, word will be of length 2^i-1.