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
