0 votes 0 votes L(G)={$a^mb^n$|m>n>=1} is the language context free? Theory of Computation grammar + – aditi19 asked Aug 26, 2018 aditi19 613 views answer comment Share Follow See all 12 Comments See all 12 12 Comments reply aditi19 commented Aug 26, 2018 reply Follow Share S->aaSb|aab|aaA A->aAb|b is this grammar correct for the given language? 0 votes 0 votes Deepanshu commented Aug 26, 2018 reply Follow Share @aditi19 FROM YOUR GRAMMAR aaab IS NOT GENERATING 0 votes 0 votes Deepanshu commented Aug 26, 2018 reply Follow Share FROM MY PRESPECTIVE IT IS CONTEXT FREE . AS WE HAVE TO SAVE VALUE OF m SOMEWHERE THAT WHILE COUNTING AND COMPARED IT TO n. it is not one of my good topics. so its just my prespective so please provide answer from where u read 0 votes 0 votes SHUBHAM SHASTRI commented Aug 26, 2018 reply Follow Share here 2 comaprisions are needed ...that can not be done by Single Stack ...so its not CFL 0 votes 0 votes Deepanshu commented Aug 26, 2018 i edited by Deepanshu Aug 26, 2018 reply Follow Share @SHUBHAM SHASTRI please little elaborate ,, at first i am also like two stacks 1 for m then for comparisons with n BUT we can also do it in one stack as at starting we put epsilon of stack then whole m while deleting n with m if we reach epsilon then goes to some dead state if not then accept CORRECT ME IF I AM WRONG 0 votes 0 votes SHUBHAM SHASTRI commented Aug 26, 2018 reply Follow Share can you please share the image of PDA ...?? 0 votes 0 votes aditi19 commented Aug 26, 2018 reply Follow Share it will go into dead state. here qd is the dead state. found this solution. i'm trying to construct the grammar for the given language 0 votes 0 votes Deepanshu commented Aug 26, 2018 reply Follow Share @aditi19 IT IS CFL THEN?????? 0 votes 0 votes aditi19 commented Aug 26, 2018 reply Follow Share yes @Deepanshu if PDA exists then it is CFL 0 votes 0 votes Deepanshu commented Aug 26, 2018 reply Follow Share @SHUBHAM SHASTRI can you please share the image of PDA ...?? MY MOBILE IS NOT IN GOOD CONDITION :( :( 0 votes 0 votes Mizuki commented Aug 26, 2018 reply Follow Share It is definitely CFL. Since you map every b for a and remove corresponding number of a's and eventually if you are left with any number of a > = 1 then you accept it. 0 votes 0 votes gauravkc commented Aug 26, 2018 reply Follow Share It is a CFL. And I think this is the grammar for it. $S\rightarrow aaABb$ $A\rightarrow aA|\epsilon$ $B\rightarrow aBb|\epsilon$ 0 votes 0 votes Please log in or register to add a comment.
3 votes 3 votes Yes it should he CFL please correct me of I am wrong SHUBHAM SHASTRI answered Aug 26, 2018 SHUBHAM SHASTRI comment Share Follow See all 0 reply Please log in or register to add a comment.