922 views

3 Answers

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

selected by
2 votes
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.

0 votes
0 votes
  1. you need two comparison
  2.   m=<n and n<=3m   so it must be CSL not CFL
reshown by

Related questions