6 votes 6 votes L={$a^m$$b^n$ | m <= n <= 3m } Theory of Computation theory-of-computation identify-class-language + – rahul sharma 5 asked Nov 11, 2017 rahul sharma 5 1.0k views answer comment Share Follow See 1 comment See all 1 1 comment reply reboot commented Dec 26, 2020 reply Follow Share yes CFL but not DCFL. We can re-write this question as L = ( {$a^{m}b^{n}$: m =n or m=2n or m=3n}). 0 votes 0 votes Please log in or register to add a comment.
Best answer 6 votes 6 votes L={ambn | m <= n <= 3m } CFG: S->aSb / aSbb / aSbbb / Ɛ PDA: For each 'a' either push 1 or 2 or 3 a's in stack and for each 'b' pop from stack. Hence,CFL but not DCFL VS answered Nov 26, 2017 • selected Nov 27, 2017 by Manu Thakur VS comment Share Follow See all 6 Comments See all 6 6 Comments reply Show 3 previous comments Manu Thakur commented Nov 27, 2017 reply Follow Share @VS I think CFG is correct for the given CFL. 0 votes 0 votes Rupendra Choudhary commented Nov 27, 2017 reply Follow Share Hello Rahul pardon for my wrong answer. your language is actually CFL. i forget to add that language would be certainly at least CSL but for CFL , we have to check because not closure means May or May not.. as VS generated CFG for given language and if there exists at least one CFG for any language then language must be CFL. 0 votes 0 votes Rupendra Choudhary commented Nov 28, 2017 reply Follow Share Hello abhishek what you're asking is , work of NPDA , with power of 'choices' it will handle this work. 0 votes 0 votes Please log in or register to add a comment.
2 votes 2 votes You have Language L which is intersection fo L1 and L2. L1 : which is set of languages of type {ambn | m<=n} // DCFL L2 : which is set of languages of type {ambn | n<=3m} // DCFL L=L1∩L2 //DCFL ∩ DCFL is at least CSL. So now language is at least CSL means we can't say not CFL. so lets check for CFL We have two ways to prove 1st way) generate some CGF for given language and we have one S->aSb|aSbb|aSbbb|Ɛ // so language is CFL 2nd way) draw PDA PDA would be like for every 'a' push 3 'a's into stack and then for every occurance of b , non deterministically pop 1'a' or 2'a' or 3'a'. There won't be any deterministic way , we have to make several choices for same i/p. Rupendra Choudhary answered Nov 11, 2017 • edited Nov 28, 2017 by Rupendra Choudhary Rupendra Choudhary comment Share Follow See all 4 Comments See all 4 4 Comments reply rahul sharma 5 commented Nov 28, 2017 reply Follow Share I have some doubt in your PDA. Lets us say i have aaabbb.Equal a and b. I push 9 a's into the stack. Now i have 3 b coming. How will we match this?We can do only 1 time pop for one b.We cannot pop 1a,2a,3a like this. ? I have two approaches in mind :- 1. we can push a 1time or 2 time or 3 time in non deterministic ways an just match with b when it comes?(like @VS said) 2. we can push a in to stack and now when b comes,i can skip two b and match with 3rd(b=3a) or i can skip one b and match with a(b=2a) or i can match b directly(a=b).At evey b i have 3 choices. Please check this and see if i am correct 0 votes 0 votes Rupendra Choudhary commented Nov 29, 2017 reply Follow Share You're right rahul.We can push in bunch but can't pop in bunch. Your approach #1 is correct one and as i'm able to see , approach #2 is wrong. Your approach will reject strings like aabbbbb. 0 votes 0 votes rahul sharma 5 commented Nov 29, 2017 reply Follow Share aabbbbb. with approach 2. Two a push to stack. Now first two b skipped and third matched with a.Again one b skipped and one matched with a.Now stack empty.and string also empty. ------------------------------------------------------------------ Two b skipped and one match gives b=3a One b skipped and next matched gives b=2a b matched with a gives b=a It think second approach is also fine.Please check once 0 votes 0 votes Rupendra Choudhary commented Nov 29, 2017 reply Follow Share ohh . i thought you're doing this process just one time but you're doing it recursively so yes! this will also work fine. it's PDA would be bit lengthy but this will also work fine. cheers for your efforts :) cheers for proving my two claims wrong :) BUt this time claim is right , i had to draw PDA for your second approach to know whether it's only theoretical approach or practically can also be implemented. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes you need two comparison m=<n and n<=3m so it must be CSL not CFL abhishek tiwary answered Nov 27, 2017 • reshown Nov 27, 2017 by abhishek tiwary abhishek tiwary comment Share Follow See 1 comment See all 1 1 comment reply jatin saini commented Nov 27, 2017 reply Follow Share It should be cfl because,we have cfg for it. And if we have cfg for a language then we can have equivalant PDA. 0 votes 0 votes Please log in or register to add a comment.