#Gatebook Qno.25

Question

Here is a CFG with only 2 variables, and a single terminal, and 2 only productions (No unit, epsilon, useless products). What would be the max number of productions if that gets converted into CNF

(A). 2

(B). <=4

(C). <=8

(D). None

Comments

plz explain??

Answer 1

s->aA

A->a.suppose it is given grammar,it contains 2 variables and 1 terminal.

max no of productions in CNF is (k-1)P+T.

here k=2,p=2,T=1.

=(2-1)2+1=3.