# Simplification of CFG

Recently i was studying removal of useless symbols in productions given in Ullman Hopcroft.

The grammar goes as follows

S-> aAa | aBC

A -> aS | bD

B - > aBa | b

C-> abb | DD

In the explanation that follows, we eliminate D obviously, but the removal of C still baffles me. As D is non generating, but C is both generating and reachable. So why delete C?

The resultant grammar is shown as

S->aAa

A->aS

B->aBa | b

Here is the link to the photo of the page in the book just in case

Page 240:

Page 241:

• Apparently Hopcroft and Ullman were wrong. There is no reason to eliminate $C$. Feb 22, 2014 at 1:58
• I though so too, so I mailed Ullman saying if this is incorrect; he replied that there is a simple explanation to this; but he wont say it because he talks only to bonafide instructors about the book and that he cannot tutor the whole world :/ Feb 22, 2014 at 2:04
• By the way, in the resulting grammar $B$ is unreachable so can be removed. Perhaps Ullman was joking with you. He's right not to answer everyone, the book is quite popular. Feb 22, 2014 at 2:58
• The grammars are not equivalent since the first produces at least the word $ababb$ while the second doesn't produce anything. Are you sure you copied the result correctly? Feb 22, 2014 at 3:45
• What edition and page is this? I could only find the 2001 edition (I think that's the second) and on pages 256 and following, the example grammar is different. Feb 22, 2014 at 4:04

The simplified grammar obviously contains a typo, as no words containing b are derivable contradicting S -> aBC -> abC -> ababb which the original grammar allows.
The first rule should probably read S -> aAa | aBabb.