Deletion of Useless Symbols from a Grammar Self Doubt

Question

S →  AB/a

A → BC/b

B → aB/C

C → aC/B


How do we remove useless symbols and productions from this grammar?

While solving, i found that the useful symbols are {a,b,S,A}

Hence, we must delete B,C

But don’t know how to proceed

Comments

If there is any B or C in transition , just remove it.

S->a
A->b

These two transition will exists at last

---

@srestha A is also useless right? since it cannot be reached from S.

Ans will be S->a

Answer 1

Every variable should derive some terminal strings and every variable should be reachable from Start symbol, then the symbol is Useful.

Useful: {a,b,S,A}

Useless: {B,C}

Now delete B and C on LHS wherever B,C exist.

S → a

A → b

 Now we can’t reach to A from S, so delete A also.

S → a is the answer

 

Answer 2

w(s)= {s}, W(s)= {S}

W(A)= {A}, W(A)= {A}

W(B)= {B}, W(B)= {B,C}

W(C)= {C}, W(C)= {C,B}

Therefor the reduced grammar is:

P’ = {S—> AB, S→ a, A→ BC, A→ b, B→ aB, B→ ac, C→ aC, C→aB}