Is the language L = { a^n b^j : j ≤ n ≤ 2j − 1 } context-free?

Is the language L = { aⁿb^j : j ≤ n ≤ 2j − 1 } context-free? I have no idea how to start with this exercise. I am familiar with the pumping lemma, but I have no idea how I should use it here. It seems to me that this language is context-free and that something could be done with the stack to realise it, but I do not know how. So if someone could give me a hint to start, I would highly appreciate it.

I took this exercise from the book 'Formal languages and automata', fifth edition, by Peter Linz, exercise 8.1.14

After some help in the comments, I thought of the following grammar:

S-> aSb|aaaSbb|λ

I claim the language L is generated by the following context-free grammar G, with starting symbol S and an additional non-terminal T:

0. S ↦ aaSb
1. S ↦ aTb
2. T ↦ aTb
3. T ↦ ε (the empty string)

Showing this grammar is a valid presentation of the language will prove the language is context-free.

Proof. (L ⊆ G). We notice that any n such that j ≤ n ≤ 2j − 1 can be written as a sum n = j + k, with 0 ≤ k < j. We also notice the case j = 0 is impossible, because the condition then implies 0 ≤ −1. To generate a string a^j+kb^j with 0 ≤ k < j, 1 ≤ j, we apply:

0. rule (0) k times, obtaining a^2kSb^k; then
1. rule (1) once, obtaining a^2k+1Tb^k+1; then
2. rule (2) j − (k + 1) times, obtaining a^j+kTb^j, and finally
3. rule (3) once, obtaining the desired string a^j+kb^j.

Therefore every string of L is generated by G.

(G ⊆ L; sketch). By induction over grammar rules. Observe that every string G can generate has the form aⁿZb^j where n, j ∈ ℕ, and Z is a non-terminal or the empty string. Then observe that:

• at the start, we have Z = S and n = j = 0;
• rule (0) can only be applied when Z = S, it maintains Z = S and the invariant n = 2j;
• rule (1) can only be applied when Z = S, it sets Z = T and n = 2j − 1, which satisfies the invariant of L that j ≤ n < 2j;
• rule (2) can only be applied when Z = T, it maintains Z = T and the invariant of L, and
• rule (3) can only be applied when Z = T, it sets Z = ε and otherwise also maintains the invariant of L.

The only way to eliminate non-terminals is to pass rule (3), and that can be only applied after rule (1). Therefore every string generated by G belongs to L.

As such, L and the language generated by G are the same language. Because G is a context-free grammar, the language L is context-free. ∎