The Gateway to Computer Science Excellence
+6 votes
L={$a^m$$b^n$ | m <= n <= 3m }
in Theory of Computation by Boss (25.6k points) | 137 views

3 Answers

+6 votes
Best answer

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

by Boss (10.9k points)
selected by

VS  how your machine going to identify for 1b you need 1a or 2a or 3a  even by multiple machine copy also??


Same doubt.Please clear. I think it is CSL as mentioned by Rupendra Choudhary 

CFG so cfl
@VS I think CFG is correct for the given CFL.
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.
Hello abhishek

what you're asking is , work of NPDA , with power of 'choices' it will handle this work.
+2 votes

You have Language L which is intersection fo Land 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.

by Boss (14.7k points)
edited by
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
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.
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
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
  1. you need two comparison
  2.   m=<n and n<=3m   so it must be CSL not CFL
by Active (3.6k points)
reshown by
It should be cfl because,we have cfg for it.

And if we have cfg for a language then we can have equivalant PDA.

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,366 answers
105,265 users