Identify the language

Question

L = ( {a^mb^n: m ≤ n ≤ 2m}).

Is the CFL or not???

Comments

https://gateoverflow.in/169022/toc-identify-class-of-language

---

Rahul , it's CFL.

i'll rectify my answer there.

---

yes CFL but not DCFL. We can re-write this question as L = ( {$a^{m}b^{n}$: m =n or m=2n}).

Answer 1

S-->aSb/aSbb/NULL

Above is cfg for given language.

Comments

If CFG is possible then it is CFL?

But I'm unable to think PDA for this.

How will I accept the string. aaabbbbb ?

---

Here we can have NPDA.

The below NPDA is for language  ={a^n b^m:n<=m<=3n}

Similarly we can also have npda for given language.

All transitions are same except for third transition on a.

In npda we can have multiple copies of stack.

So for your i/p aaabbbbb for first two a  we push 2b and for last a we push one b into the stack,and string will be accepted.