[Solved]: Chomsky Normal Form-remove unit production

Problem Detail: 

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??

Asked By : Karen

Answered By : Renato Sanhueza

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.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/43678