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:
- Add a new start variable and point it to the old start variable
- 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
- Remove all of the unit rules, and adjust the grammar such that it produces the same language
- 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 )
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
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?