4 votes 4 votes radha gogia asked Dec 7, 2015 radha gogia 3.2k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
1 votes 1 votes Simply reverse the grammar. Ex; A→Aa/a(left rec) Reverse the grammer A→aA/a(right rec) You can do vice versa.Note : In case of Left Linear or Right Linear not for all. ManojK answered Dec 7, 2015 • edited Dec 7, 2015 by ManojK ManojK comment Share Follow See all 9 Comments See all 9 9 Comments reply Praveen Saini commented Dec 7, 2015 reply Follow Share Well it is not correct or correct way to do so. suppose we have given left linear grammar having language L for it. and if follow that way, we will get right linear but that will represent language LR. or vice-versa. we can do it in any grammar (not only left/right linear ) to find the reversal. 0 votes 0 votes ManojK commented Dec 7, 2015 reply Follow Share Yes sir i think it will represent LR but not L. 0 votes 0 votes ManojK commented Dec 7, 2015 reply Follow Share But this is not correct way to convert RLG TO LLG. suppose we have given any right linear grammer. First we have convert it into Finite automata. Then reverse the Finite autome. We get Right linear grammar representing L^r. Now reverse the the right Linear grammar we get Left linear grammar repsenting L 1 votes 1 votes Praveen Saini commented Dec 7, 2015 reply Follow Share Yes, it is correct. :) for left/right linear. But left-recursive and right-recursive grammar is much more that left/right linear grammar. (ex. S->SAY, A->XA|a , X->Yb,Y->aY|b ) btw In any case it can be done without FA. As we do in while converting CFG to GNF. :) 0 votes 0 votes ManojK commented Dec 7, 2015 reply Follow Share Yes sir we can do it CGF to GNF conversion. But Sir i m puzzled in Right recursive grammar to left recursive bcz in CFG to GNF conversion we eliminate Left recursion.Is there any algo to convert Right recursive grammar to left recursive grammar. 0 votes 0 votes Praveen Saini commented Dec 7, 2015 reply Follow Share Yes, there is a way, as simple as in left-recursive. a little analysis of grammar. I would like to answer it in morning. :) 0 votes 0 votes ManojK commented Dec 7, 2015 reply Follow Share ok sir 0 votes 0 votes Mahesha999 commented Jan 21, 2016 reply Follow Share @Praveen Saini have answered this elsewhere? 0 votes 0 votes Mahesha999 commented Dec 29, 2016 reply Follow Share I guess ManojK's solution applies to regular/linear grammars (LLG and RLG). Can we convert left recursive CFG to right recursive CFG and vice versa? 0 votes 0 votes Please log in or register to add a comment.