-1
$\begingroup$

My professor have asked me strange question , about converting from Context free grammar to chomsky normal form , Can we remove unit productions first from CFG if possible , before removing null productions , does it effect the Chomsky normal form ?

$\endgroup$
  • 2
    $\begingroup$ What do you think? Have you tried it? $\endgroup$ – Yuval Filmus Jul 26 '15 at 20:04
  • 1
    $\begingroup$ yes , i have but gives new CNF $\endgroup$ – Zulqurnain Jutt Jul 26 '15 at 20:59
  • 2
    $\begingroup$ So then it sounds like you've answered your own question? If you have an example where removing null productions yields a different Chomsky normal form than when not removing null productions, you have an answer. Would you like to write up an answer that answers your own question, with a detailed example and explanation? $\endgroup$ – D.W. Jul 26 '15 at 23:37
  • $\begingroup$ Why would it be a problem if you get another CNF grammar? I don't think anyone claims that the CNF of a CFG is unique. $\endgroup$ – Raphael Jul 27 '15 at 6:25
  • 1
    $\begingroup$ @babou In my experience, textbooks will present a couple of theorems of the form "Every CFG with X can be transformed into an equivalent one with X plus Y" that lead from an unrestriced CFG via reduced and then chain-rule-free grammars to CNF. The observant reader will be able to decide if the theorems resp. the constructions from the proofs can be applied in any sequence. Hence my comment and downvote: the OP should have enough material at hand to investigate on their own, and the question in its current form suggests that they did not bother to. $\endgroup$ – Raphael Jul 27 '15 at 11:28
0
$\begingroup$

There is no problem in removing the unit productions first except when in the next step while removing the null productions the grammar might be transformed into one which again has unit productions and you have to repeat the steps again to reach a cnf.

$\endgroup$

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.