In the step of removing unit productions when converting a grammar to Chomsky normal form, I sometimes found that the variables may end up having the same production bodies. Is this possible? If so, can we consider these variables identical? For example, given:



S-derivable set is {A, B}
A-derivable set is {B, S}
B-derivable set is {S, A}

If I add all the non-unit productions from A and B to S, and from B and S to A, and from S and A to B, then the resulting new productions of S, A and B will have exactly the same production bodies.

A->same as above
B->same as above

Is this correct??

  • 1
    $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ – Raphael Jun 17 '15 at 9:05

Yes it is correct. This happened because in your original grammar the non-terminal symbols formed a cycle with the following productions: $$S\to A$$ $$A\to B$$ $$B\to S$$

So by transitivity all non-terminals can produce the same things.

| cite | improve this answer | |
  • $\begingroup$ So since the body of production are the same for S, A, and B, can these variables be viewed as identical? In other words, can this grammar be simplified? $\endgroup$ – Karen Jun 17 '15 at 2:46
  • $\begingroup$ Im not familiar to the concept of variables in grammars. I use the terms: terminal symbols$(a,b)$ and non-terminal symbols$(S,A,B)$. So in your grammar described by it's production rules, I can say that the non-terminal symbol $S$ can be replaced with the same things as $A$ or $B$. $\endgroup$ – Renato Sanhueza Jun 17 '15 at 2:52
  • $\begingroup$ I think variables = non-terminal symbols. So finally, the above 3 productions can be simplified to only one: S->aSS|aS|S|bSSS|bSS|bS|a|b. Is this correct? $\endgroup$ – Karen Jun 17 '15 at 2:56
  • $\begingroup$ You can write infinite amount of grammars that denotes a particular language(for example replacing the non-terminal symbols with others). The Chomsky Normal Form is a good example of rewrite a grammar. The only difference is that CNF has particular rules given by his definition. So yes you can eliminate the non-terminals $B,C$ and still denote the same language changing all $A's$ and $B's$ for $S's$ but it is not necessary and not required for your exercise. $\endgroup$ – Renato Sanhueza Jun 17 '15 at 3:08

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.