Ullman (TOC) Edition 3 Exercise 7.1 Question 1 (Page No. 275)

Question

Find a grammar equivalent to

$S\rightarrow AB|CA$
$A\rightarrow a$
$B\rightarrow BC|AB$
$C\rightarrow aB|b$

with no useless symbols.

Answer 1

Given Grammar is:

$S\rightarrow AB/CA$

$A\rightarrow a$

$B\rightarrow BC/AB$

$C\rightarrow aB/b$

Now we can see that $B\rightarrow BC/AB$ cannot reach a terminal as it end or starts with B itself. So, the production of B can be removed.

Now. the grammar becomes:

$S\rightarrow AB/CA$

$A\rightarrow a$

$C\rightarrow aB/b$

Now all the productions involving B can be removed.

Hence, finally, the grammar becomes

$S\rightarrow CA$

$A\rightarrow a$

$C\rightarrow b$

Comments

I think you can even simplify it further as S→ba.

---

No, we cannot do that. The question is about removing useless symbols.