0 votes 0 votes L1 = {an bm | n ≤ m ≤ 2n} L2 = {an bm│m≠n & m≠2n} Which of the following is true? A. Only L1 is CFG B. Only L2 is CFG C. Both are CFG D. None of them is CFG Theory of Computation theory-of-computation context-free-grammar normal + – AmitPatil asked Jan 26, 2017 • retagged Jun 4, 2017 by Arjun AmitPatil 827 views answer comment Share Follow See all 12 Comments See all 12 12 Comments reply erh commented Jan 26, 2017 i edited by erh Jan 27, 2017 reply Follow Share Yes , the both languages are CFL . more precisely it will be accepted by NPDA but not by DPDA, Hence it is CFL but not DCFL .The language can seen as anbm such that either n<=m or m<=2n. Similarly, the other can also be accepted by NPDA. You can push non-deterministically "a" and "aa" into the stack and pop "a" on when the input symbol is "b". 0 votes 0 votes rajatmyname commented Jan 27, 2017 reply Follow Share I think (c) is answer 0 votes 0 votes cse23 commented Jan 27, 2017 reply Follow Share I think L2 is not CFL only L1 is CFL 0 votes 0 votes Sushant Gokhale commented Jan 28, 2017 reply Follow Share Both are CFL. First NPDA, Second DPDA 0 votes 0 votes Abbas2131 commented Jan 28, 2017 reply Follow Share How is the second one CFL.? 0 votes 0 votes Rahul Jain25 commented Jan 28, 2017 reply Follow Share Both are requiring two comparisons how cfl?? 0 votes 0 votes Abbas2131 commented Jan 28, 2017 reply Follow Share The first one is a CFL S-> aSb| aSbb| epsilon I dont know about the second one I tried to play with the productions but always came up wotha grammer that accpted NOT ALL strings which had n!=m or n!=2m 0 votes 0 votes Sushant Gokhale commented Jan 29, 2017 reply Follow Share The second one: Push 2a for each a. Now, popping function is for each b, pop 2a. Case 1: If b is greater than 2a, then b will remain Case 2: if b is less than a, then a will remain. 0 votes 0 votes Sandeep Suri commented Jan 29, 2017 reply Follow Share Yes @Sushant both are CFL 0 votes 0 votes Abbas2131 commented Jan 29, 2017 reply Follow Share Thank you , got it. Its a NCFL 0 votes 0 votes akhileshreddy commented Jul 13, 2017 reply Follow Share can anyone please provide cfg for the above languages as well. 0 votes 0 votes prayas commented Jan 12, 2018 reply Follow Share @ Sushant Gokhale This only proves that m!=2n.If we go by your algorithm we would never be able to say whether n!=m. 0 votes 0 votes Please log in or register to add a comment.