CFL - Problem Test Series

Question

L={a^n b^k, n <= k <=2n}

1.CFL

2.Non CFL

Comments

https://gateoverflow.in/92299/context-free-languagev

Answer 1

it is CFL because it can Non-deterministic PDA can solve this.

k will either be n,n+1,n+2,.....,2n.

Now non-deterministic PDA can run them to find out which one satisfies it.

Thus it is CFL.

Comments

are you sure about this? I think 2 stacks might be required here and might be CSL.How to compare n<k and k<2n at the same time using one stack? We can push n no of a's at first then if you apply non determinism also how will you remember if it is less greater than n or less than 2n, you dont have a fixed value for n.

---

NPDA WILL ACCEPT THIS,BCZ NPDA IS SUM UP ALL STACK REQUAIRED IN THIS LANGUAGE,FOR ALL STATE AUTOMATION.TOTAL NO OF n STACK REQUIRED AT MOST.

---

now I see it thanks..