Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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?
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.
Is it necessary to remove [lambda/unit rules] before converting [a CFG to CNF or GNF]?
No, but it is necessary to remove them as a part of the conversion, because the definition of CNF and GNF imply that they do not occur in a grammar on those normal forms.
