Suppose a CFG has unit productions A -> B and C -> D among other productions, possibly involving A,B,C,D and possibly other symbols too. The method of eliminating these unit productions, to get a CNF, which I've learned in class, I can describe for A -> B. I'm supposed to look at every production rule in the grammar, and find every permutation of substituting A for B or not.

For instance, if the rule includes X -> AAB then to eliminate A -> B for this rule, I should find the permutations X -> AAB|BAB|BBB|ABB which are added to the grammar, and the rule A -> B is then eliminated.

My question is, does it ever matter if you eliminate A -> B first and then C -> D, versus doing them in reverse order?



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.