2 votes 2 votes Consider the following grammar $S\rightarrow Aa\mid B $ $B\rightarrow a\mid BC$ $C \rightarrow a\mid \in$ the no of productions in simplified cfg is Compiler Design compiler-design context-free-grammar + – Pooja Palod asked Oct 26, 2015 • retagged Jun 17, 2022 by Lakshman Bhaiya Pooja Palod 3.4k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Digvijaysingh Gautam commented Oct 18, 2016 reply Follow Share I think 4 ? 0 votes 0 votes Shubhanshu commented Sep 25, 2017 reply Follow Share 5??? 0 votes 0 votes G.K.T commented Sep 25, 2017 reply Follow Share we may remove A as its of no use now S is producing only B so instead of that we may also remove S and make B as starting symbol and in B , C is Producing only a/NULL so we may substitute in B and it would be like B --> a/ba/b 0 votes 0 votes Deepak Poonia commented Sep 26, 2022 reply Follow Share These type of questions are Poorly framed & Non-sense as the answer depends on the Algorithm that is being used here. You can study different standard books Or standard resources, apply their “Null Production Removal Algorithm” on this question, you’ll get different answers. Also, the problem of finding a Smallest CFG is Not easy, seems NP Hard Or undecidable, Not Sure. Students should Avoid such Poor Questions & the sources which ask them. 0 votes 0 votes Please log in or register to add a comment.
Best answer 4 votes 4 votes 1.Removal of null production S->Aa|B B->a|B|BC C->a 2.Removal of Unit production S->Aa|a|BC B->a|BC C->a 3.Removal of useless production S->a|BC B->a|BC C->a so total 5 production in simplified CFG. Umang Raman answered Oct 26, 2015 • selected Aug 31, 2018 by Shaik Masthan Umang Raman comment Share Follow See all 4 Comments See all 4 4 Comments reply Shubhanshu commented Aug 29, 2017 reply Follow Share Why you have removed S -> Aa A is variable here?? 0 votes 0 votes Sandeep Suri commented Oct 26, 2017 reply Follow Share But you can't reachA from S therefore we removed it 0 votes 0 votes Shubhanshu commented Oct 26, 2017 reply Follow Share Do we remove, A because its definition is not present in the grammar?? 0 votes 0 votes 92komal commented Dec 22, 2017 reply Follow Share plz give me proper explanation why A is not removed in that grammer 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes We can remove Aa as A is not defined. S->B B-->a|bC C-->a|eps now, S->B is unit production S-->a|bC C-->a|eps removing epsilon production, S-->a|b|bC C-->a So, simplified CFG contains 4 productions. Anusha Motamarri answered Sep 28, 2016 Anusha Motamarri comment Share Follow See all 3 Comments See all 3 3 Comments reply Pankaj kumar commented Sep 28, 2016 reply Follow Share @kapil is it necessary to write production S -> bC 0 votes 0 votes Kapil commented Sep 28, 2016 reply Follow Share yes, Even if you want to replace C value, then, S->a | b | bC | ba (still 4 productions) 0 votes 0 votes Pankaj kumar commented Sep 28, 2016 i edited by Pankaj kumar Sep 28, 2016 reply Follow Share ok i got it. 0 votes 0 votes Please log in or register to add a comment.
4 votes 4 votes It's 4.. firstly epsilon is removed from C.. making C->a and B->a|b|bC and den unit production S->B is replaced by production of B making S->a|b|bC and also Aa is removed from S coz of useless symbol.. so total production will be S->a|b|bC C->a That's 4... kirti singh answered Oct 18, 2016 kirti singh comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments cse23 commented Oct 18, 2016 reply Follow Share Wherever I studied it was in sequence only: If G is a CFG , then we can construct a simplified equivalent CFG G’ with the help of following steps: 1. Eliminate all null productions. 2. Eliminate all unit productions 3. Eliminate all useless productions 2 votes 2 votes kirti singh commented Oct 19, 2016 reply Follow Share @devwritt yes.. if any of the following things is in production rule.. den dey must be eliminated in the order.. order of elimination matters.. so eliminate in order as 1.null production 2.unit production 3.useless symbols 0 votes 0 votes Devwritt commented Oct 19, 2016 reply Follow Share Okay okay, Thanks. Got it 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes S->a|b|bC C->a hence 4 productions. Pankaj kumar answered Sep 27, 2016 • edited Sep 28, 2016 by Pankaj kumar Pankaj kumar comment Share Follow See all 0 reply Please log in or register to add a comment.