# Context Free Language Twist [duplicate]

I am trying to recognize a particular language,

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

and according to me it should not be CFL, as i can see two comparision i.e. firstly number of a is compare to keep count less than equal to k, and secondly for count of b that should be less than twice n. My question then how it is still CFL??

If you're using grammars, then this is easy to see: $$S\to aSb\mid aSbb\mid \epsilon$$ That is, each $$a$$ corresponds to either 1 or 2 $$b$$'s.
If you're thinking about it from the automata perspective, then a PDA can push to the stack $$n$$ symbols while reading $$a^n$$, and then start popping those symbols upon reading $$b^k$$, with the following change: it may nondeterministically choose not to pop a symbol, but the it moves to a new state from which it must pop a symbol after reading $$b$$. This ensures that the number of $$b$$'s that are read is between $$n$$ and $$2n$$.
• No, because after not popping a symbol upon reading $b$, you move to a new state where you have to pop upon reading $b$, and then go back to the first state. Oct 21, 2022 at 6:06