4
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\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, 2013 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, 2013 at 15:33

1 Answer 1

Reset to default
2
$\begingroup$

  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 \rightarrow a\ |\ A \in N,\ a \in \Sigma$

    • Type 2: $A \rightarrow BC\ |\ A,B,C \in N$

    Nothing less and nothing more.

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

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

It is important to notice that when you have $\epsilon$ 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 languages although the differences can be considered trivial.

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

Polishing the grammar could be mandatory in a practical context.

  1. I still don't know anything about Greibach normal form so good luck!
Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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