[Solved]: Converting context-free grammar to Chomsky/Greibach Normal Form

Problem Detail: 

Is it necessary to remove all lambda productions, unit productions and useless productions from a context free grammar(CFG) before converting to Chomsky Normal Form(CNF) or Greibach normal form (GNF). If so why is it required?

Also my Professor said that we should convert a CFG into CNF before converting it to GNF. Is that required or can we straight away convert a CFG into a GNF?

Asked By : Abhishek Dhankar

Answered By : Yuval Filmus

You can convert a context-free grammar into Chomsky normal form or Greibach normal form in whatever way you wish (converting a grammar to a normal form means finding a grammar in the normal form which generates the same language as the original grammar). A given algorithm might require you first to remove lambda productions, or first to convert to Chomsky normal form. If using a specific algorithm, you have to follow whatever the algorithm prescribes.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/54460

 Ask a Question

 Download Related Notes/Documents