I could find that different texts follow different steps in the conversion of CFG to Chomsky Normal Form. I couldn't find any presumptions they made in the conversion steps. I have some questions regarding the conversion.

  1. Most text books tell us about only two rules $A \rightarrow BC$ and $A \rightarrow a$. But some texts say that starting productions should not be in the right hand side. Why some stress on that rule and others not?

  2. When talking about the rules some don't stress much on the condition of removing useless symbols. Is this condition mandatory or not?

  3. Which is the best rule? Remove useless production, remove $\epsilon$ production, remove unit production, adjust the resulting productions so as to reflect the CNF rules.

  4. Converting a grammar to Greibach normal form requires first converting the productions to Chomsky Normal Form?

  • $\begingroup$ For 1 to 3, I think these are mostly matters of taste. Pick of them what you like. Unless you're student, studying for exams. In that case, ask you professor what he prefers. $\endgroup$ – Karolis Juodelė Mar 28 '13 at 17:20
  • $\begingroup$ 2 is "morally mandatory" because you don't want to use productions that you in fact will never use (because they never seems to be builded by the related grammar) or reach (like unreachable non-terminals). When you are programming, if the grammar contains such things, you will "have" to program those unnecesary productons... better if they doesn't appear. My guide anyways is the Hopcroft, Ullman & Motwani Introduction to Automata Theory, Languages and Computation. $\endgroup$ – Alejandro Sazo May 5 '13 at 15:33

1.-The definition that my teacher told me about CNF: It is a context-free language whose productions are from two types:

Type 1: A−>a|A∈N,a∈Σ

Type 2: A−>BC|A,B,C∈N

Nothing less and nothing more.

2.-You can always simplify a CFL but that is not necessary. At least from a theorycal point of view.

3.- There isn't best rule. Remove useless production is just a way you can polish your CFL.

It is important to notice that when you have ϵ productions you don't meet the requirements for a context-free grammar so you can't make the conversion to CNF. If you eliminate those productions you are generating a CFG very similar to the original grammar but not equivalent . They denote different languajes although the differences can be considered trivial.

Then you mention "remove unit productions" and "adjust resulting productions" this are the steps of the algorithm to convert a CFG in a CNF.

Polish the grammar could be mandatory in a practical context.

4.- I still don't know anything about Greibach normal form so good luck!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.