[Solved]: Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?

Problem Detail: 

$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$

Asked By : emmy

Answered By : Ran G.

It is context Free.

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.

More information you can find in this question.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10635