Peter Linz Edition 4 Exercise 6.1 Question 6 (Page No. 161)

Question

Eliminate useless productions from

$S\rightarrow a|aA|B|C,$

$A\rightarrow aB|\lambda,$

$B\rightarrow Aa,$

$C\rightarrow cCD,$

$D\rightarrow ddd.$

Answer 1

Step 1: First we remove all those variable who can't derive a terminal string

               so we remove productions C ->cCD

Step 2: Now we remove all those variables who can't be reached from the start symbol

            so we remove production D -> ddd

Answer 2

C can never terminate

after removing C ,D can’t be reached

the remaining grammer is

 

S→  a | aA | B,

 A→  aB |  λ,

B→Aa

after solving λ productions

S→  a | aA | B,

 A→  aB

B→Aa

now unit productions

S→  a | aA | Aa,

 A→  aAa

B→Aa

and now we can’t reach to B so we can remove it also

S→  a | aA | Aa,

 A→  aAa