# Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \}$ context free?

$L = \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \}$

Is this language a context free language? If yes give a PDA. If no, give a proof.

The pumping lemma for context free languages doesn't seem to work here.

Let $p>1$ be the pumping length. Let the string be divided into five parts according to pumping lemma as $w = uvxyz$.

For any string of the form $a^ib^j \ s.t.$:

1. $j\lt i-1$ choose $v=a, \ x=\epsilon, \ y=\epsilon$

2. $j\gt 2i+1$ choose $v=\epsilon, \ x=\epsilon, \ y=b$

3. $j = i-1$ choose $v=a, \ x=\epsilon, \ y=b$

4. $j = 2i+1$ choose $v=a, \ x=\epsilon, \ y=b$

5. $j\gt i,\ j\lt 2i$ choose $v=a, \ x=\epsilon, \ y=b$

• Have you tried proving the opposite?
– Raphael
Mar 20 '13 at 11:20

You can see it as a union of two languages: $L_1$ where $j>2i$ and $L_2$ which is very similar to the one of this question.