#Gatebook Qno.26

Question

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

(A). 2

(B). <=4

(C). <=8

(D). None

Comments

is given answer option d)none?

---

i don't know but how to attempt plz explain??

---

am thinking it shud be either a) or d)
one algorithm says u shud first convert given CFG to CNF and then apply rules of GNF
and another way is just making a grammar which accepts same language as given CFG and making sure the grammar is of the form V-->TV*
if the grammar is
A-->aaaaaaaaaaaaaB
B-->a
using the first algorithm if i convert this grammar into CNF rules will be greater than 8. we further convert it into GNF which will increase productions even more.
this way am gettting >8

and another way, creating the grammar which follows GNF rules
then
A--> aXXXXXXXXXXXXB
X-->a
two are enough!
anybody conform do we need to convert given CFG to CNF before converting to GNF?
peterson says we need not.
and
http://www.iitg.ernet.in/gkd/ma513/oct/oct18/note.pdf
iitg says we shud