Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free?

Question

Is the language $L = \{ a^ib^j \mid i\ \nmid\ j \ \} $ context free ?

If we fix $n \in N$ then we know that the language $L = \{ a^ib^j \mid \ \forall \ 1 \le k \le n \ , \ \ j\neq ki \} $ is context free (as it can be presented as a finite union of context free languages in a similar way to the example here: Is $L= \{ a^ib^j \mid j\neq i \ and \ j\neq2i \ \} $ context free?)

I think that it's not context free but have failed to prove it. By reading other questions on this site I noticed this interesting observation: CFL's in $a^*b^*$ are closed under complement as can be seen here: Are context-free languages in $a^*b^*$ closed under complement?

So our language $L$ is context free if and only if $ \bar L = \{ a^ib^j \mid \ \ i\ \mid\ j \ \} $ is context free. I tried using the pumping lemma but to no avail.

Thanks in advance

Answer 1

If I'm not mistaken, you can pump $\bar L$ using $\sigma = a^{n}b^{n^{2}}$, because $n \mod n^{2} = 0$. The result is that $\bar L$ is not context free. The property that you mentioned has an "iff", then $L$ is not context free.

Answer 2

Using $\sigma = a^nb^{n^2}$(in $\overline{L}$) you can pump any amount of b's you want and pumping lemma is fulfilled.

Consider $\sigma= uvwxy$ with $vx$ a secuence of b's and $\sigma'=uv^iwx^iy$ with $i \in \mathbb{N}_0$.

Then the amount of a's in $\sigma'$ is constant $n$, the amount of b's is $n^2 + |vx| (i-1)$ and $1\leq|vx|\leq n$ (pumping lemma).

So if you choose the descomposition with $|vx|=n$ you can always divide $n^2+n(i-1)=n(n+i-1)$ with $n$ a's $\forall i$.

Finally we can't use pumping lemma in this demostration(Im doomed).

Answer 3

it is CFL. consider this CFG

S --> X | Y

X --> aXb | aX | a

Y --> aYb | Yb | b