1 votes 1 votes 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 Theory of Computation grammar theory-of-computation + – Sukhbir Singh asked Apr 30, 2019 Sukhbir Singh 503 views answer comment Share Follow See all 2 Comments See all 2 2 Comments reply srestha commented Apr 30, 2019 reply Follow Share If there is any B or C in transition , just remove it. S->a A->b These two transition will exists at last 1 votes 1 votes Ayan Kumar Pahari commented Jun 3, 2020 reply Follow Share @srestha A is also useless right? since it cannot be reached from S. Ans will be S->a 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes 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 Rajat Agrawal007 answered Oct 20, 2021 Rajat Agrawal007 comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes 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} Shivyanshi shukla answered Nov 13, 2021 Shivyanshi shukla comment Share Follow See all 0 reply Please log in or register to add a comment.