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

D -> aDa

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:
C isn't Part of the grammar recursion. As it expands to Terminals only, it is artificial in the Sense That it is only used for notational convenience while it is unnecessary for expressing the CFG.

The simplified grammar obviously contains a typo, as no words containing b are derivable contradicting S -&gt; aBC -&gt; abC -&gt; ababb which the original grammar allows.

The first rule should probably read S -&gt; aAa | aBabb.