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

The Gateway to Computer Science Excellence

+6 votes

Best answer

0

0

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.

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.

+2 votes

You have Language L which is intersection fo L_{1 }and L_{2}.

L_{1} : which is set of languages of type {a^{m}b^{n} | m<=n} // DCFL

L_{2} : which is set of languages of type {a^{m}b^{n} | n<=3m} // DCFL

L=L_{1}∩L_{2} //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.

0

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

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

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.

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

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

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

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.

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,321 answers

198,400 comments

105,155 users