# Chomsky Normal Form-remove unit production

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->aAA|aA|A|a
A->bBBB|bBB|bB|B|b
B->bSSS|bSS|bS|S|b


So

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.

S->aAA|aA|A|bBBB|bBB|bB|bSSS|bSS|bS|a|b
A->same as above
B->same as above


Is this correct??

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$$
• 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$. – Renato Sanhueza Jun 17 '15 at 2:52
• 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. – Renato Sanhueza Jun 17 '15 at 3:08