0 votes 0 votes 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 Theory of Computation theory-of-computation test-series + – Hradesh patel asked Nov 20, 2016 Hradesh patel 411 views answer comment Share Follow See all 6 Comments See all 6 6 Comments reply Hradesh patel commented Nov 22, 2016 reply Follow Share #plz explain?? 0 votes 0 votes santhoshdevulapally commented Nov 22, 2016 reply Follow Share for GNF i don't know but for CNF grammar max no of productions is =(k-1)P+T. k= max no of symbols on right hand side production. P=total productions in the given grammar. T=max no of terminals. 0 votes 0 votes Hradesh patel commented Nov 23, 2016 reply Follow Share bro i also know this one but i ask about GNF 0 votes 0 votes Anusha Motamarri commented Nov 23, 2016 reply Follow Share is given answer option d)none? 0 votes 0 votes Hradesh patel commented Nov 23, 2016 reply Follow Share i don't know but how to attempt plz explain?? 0 votes 0 votes Anusha Motamarri commented Nov 23, 2016 reply Follow Share 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 0 votes 0 votes Please log in or register to add a comment.