0 votes 0 votes consider the following languages M and N M={W$W^{R}$W$W^{R}$ | W$\epsilon$(0,1)*} N={W1$W1^{R}$W2$W2^{R}$ | W1,W2$\epsilon$(0,1)* which of the following languages are CFL? Gate Fever asked Jan 13, 2019 Gate Fever 763 views answer comment Share Follow See all 16 Comments See all 16 16 Comments reply anjali007 commented Jan 13, 2019 reply Follow Share 2nd one is CFL? Regarding the 1st one I dont think that it is CFL It is CSL 0 votes 0 votes Gate Fever commented Jan 13, 2019 reply Follow Share see this @anjali007 if i take w= 110 w^R will be 011 right now it will become 110 011 110 011, right if u look at this the first half is reverse of next half; and this can be easily done by CFl isnt it 1 votes 1 votes Gate Fever commented Jan 13, 2019 reply Follow Share @smsubham yes i marked both, but they gave only N 0 votes 0 votes anjali007 commented Jan 13, 2019 reply Follow Share @Gate Fever ya u r right!! but will it work for every case? 0 votes 0 votes Kunal Kadian commented Jan 13, 2019 reply Follow Share Hahaha True @smsubham and by simple logic if N is CFL then M has to ne CFL, M is subset of N. In N, W1 can be equal to W2, which will make it M. Both are NCFL. 0 votes 0 votes Gate Fever commented Jan 13, 2019 reply Follow Share did u give @smsubham cbt1?? 0 votes 0 votes Gate Fever commented Jan 13, 2019 reply Follow Share both are CFL is the right option am i right @Kunal Kadian 0 votes 0 votes Kunal Kadian commented Jan 13, 2019 reply Follow Share @Gate Fever Yeah both languages have a non-deteministic PDA, both are CFL. You are right. No need to get a Fever😅 0 votes 0 votes Gate Fever commented Jan 13, 2019 reply Follow Share if u gave cbt1,can u pls tell me whether these questions have correct answer in key or not 27,31,36,52 0 votes 0 votes Kunal Kadian commented Jan 13, 2019 reply Follow Share Ahha.. didn't gave CBT.. If you can post the question, than I can give them a try. 0 votes 0 votes Fyse commented Jan 13, 2019 reply Follow Share https://cs.stackexchange.com/questions/49557/is-wwr-wwr-a-context-free-language 2 votes 2 votes Kunal Kadian commented Jan 13, 2019 reply Follow Share Omg! Yes MadeEasy is Right. In M we will use up $W$ for checking $W^r$ and then can't be sure that next $W$ is same as previous one. Got it. Thanks. 2 votes 2 votes anjali007 commented Jan 13, 2019 reply Follow Share that is the reason why a^nb^na^n is not cfl we need to check the 2nd part too so M is not CFL.. 1 votes 1 votes Gate Fever commented Jan 13, 2019 reply Follow Share yes i guess u are correct M is not a CFL because it will accept 010010 also and it is not of the desired form ww^Rww^R 0 votes 0 votes jatin khachane 1 commented Jan 13, 2019 reply Follow Share M is not cfl even if we do WWr comparision after that next w should be equal to first one ..which is not possible as nothing will on stack after wwr 0 votes 0 votes junaid ahmad commented Jan 13, 2019 reply Follow Share N is CFL,because it is a concatenation of two CFL languages M is not because we require more than one stack considering to match string in reverse and straight order. 0 votes 0 votes Please log in or register to add a comment.