Is the following language context-free?

Question

I need to show whether the language $L_2$ is context-free or not where $L_2$= $\overline{L}$ such that L= { $a^nb^m$ : 0 ≤ n ≤ m ≤ 2n }.
I am able to show that L is context-free , S­> aSb | aSbb | ε, but i don't know about $L_2$. Can you help me with $L_2$, thanks in advance.

Answer 1

There are 2 cases for $L_2$, $m<n$ and $m>2n$ so you could make a CFG $S\rightarrow A,B$ where $A$ accomplishes the first case and $B$ accomplishes the second case.

I'll let you try to figure out the rest. If you want another hint, feel free to comment!

Edit more info:

For the first case: $m<n$

$S \rightarrow aA$

$A \rightarrow aA, aAb$

With this, you have the CFG for the language $a^nb^m, m<n$

For the second case: $m>2n$

$S \rightarrow Bb$

$B \rightarrow Bb, aBbb$

Then you combine them to get:

$S \rightarrow aA,Bb$

$A \rightarrow aA, aAb$

$B \rightarrow Bb, aBbb$