4
$\begingroup$

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:

| cite | improve this question | |
$\endgroup$
  • $\begingroup$ Apparently Hopcroft and Ullman were wrong. There is no reason to eliminate $C$. $\endgroup$ – Yuval Filmus Feb 22 '14 at 1:58
  • $\begingroup$ 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 :/ $\endgroup$ – Nishad Feb 22 '14 at 2:04
  • 1
    $\begingroup$ 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. $\endgroup$ – Yuval Filmus Feb 22 '14 at 2:58
  • 1
    $\begingroup$ 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? $\endgroup$ – G. Bach Feb 22 '14 at 3:45
  • 2
    $\begingroup$ 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. $\endgroup$ – G. Bach Feb 22 '14 at 4:04
1
$\begingroup$

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 -> aBC -> abC -> ababb which the original grammar allows.

The first rule should probably read S -> aAa | aBabb.

| cite | improve this answer | |
$\endgroup$
  • 2
    $\begingroup$ Finding a minimal grammar is a completely different task than finding a reduced grammar. In particuar, iirc, the former is not computable while there are efficient algorithms for the latter. (I assume that reduced grammars are the topic here.) $\endgroup$ – Raphael♦ Feb 22 '14 at 13:28
  • 1
    $\begingroup$ In particular, reducing the grammar does not change the parse trees, while removing C in this case does change them. $\endgroup$ – babou Feb 22 '14 at 17:00

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.