0
$\begingroup$

Let's say that we have a context free grammar G, which is not in chomsky normal form, and we need to convert it to chomsky normal form.

The steps involved in the conversion are as follows:

  1. Add a new start variable and point it to the old start variable
  2. Remove all of the empty rules, except for the empty rule where the variable is the start variable, and adjust the grammar such that it produces the same language
  3. Remove all of the unit rules, and adjust the grammar such that it produces the same language
  4. Format the resultant grammar to fit the chomsky normal form

I understand all of the steps and can apply them to convert the grammar, but one thing that I am not sure of is the "order in which we eliminate the empty and unit rules". Because, apparently, if we remove unit and empty rules in wrong order then the final resultant will be wrong

My understanding is as follows: ( not sure about point 1 either )

  1. In the case of "removing empty rules": There's no order, we can remove the last rule first or the first rule last. Basically, we can remove any rule at any time

  2. In the case of "removing unit rules": There is order, but not sure what the order is?

EDIT: My question is: Let's say we are at the stage of eliminating unit rules, does it matter which rule we eliminate first? like is it okay if we remove the "new start variable pointing to old start variable" then the other unit rules or if we eliminate the other unit rules and then the new start rule etc?

Can someone help me please?

Improve this question
$\endgroup$
8
  • $\begingroup$ Do you have an example where removing unit rules led ti an incorrect answer? $\endgroup$
    – rici
    Jan 24 at 14:00
  • $\begingroup$ @rici Yes, I will add an example tonight in a few hours $\endgroup$
    – Pratik Hadawale
    Jan 24 at 14:35
  • $\begingroup$ @rici Now that I solved this problem again, turns out last time i made a mistake. Does it mean, that the order in which we make the eliminations of unit rules and empty rules does not matter? $\endgroup$
    – Pratik Hadawale
    Jan 24 at 15:52
  • $\begingroup$ you should remove empty rules first, in case a new unit rule arises as a result. Other than that, as far as I know, it makes no difference to the correctness of the result. $\endgroup$
    – rici
    Jan 24 at 17:55
  • 1
    $\begingroup$ There is some discussion on this at wikipedia: en.wikipedia.org/wiki/… $\endgroup$
    – Hendrik Jan
    Jan 24 at 18:09

0

Reset to default

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.

Browse other questions tagged or ask your own question.