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

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.

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.

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).

• You can choose $n$ larger than the pumping length, and then you are guaranteed that $|vwx| < n$. – Yuval Filmus Apr 28 '15 at 18:06
• You are right. My bad. – Renato Sanhueza Apr 28 '15 at 21:41
• Very good @RenatoSanhueza, your interest will be considered. – Alejandro Sazo Apr 29 '15 at 23:30

it is CFL. consider this CFG

S --> X | Y

X --> aXb | aX | a

Y --> aYb | Yb | b

• You grammar is for the language $\{a^{i}b^{j} \mid i \neq j\}$, the question is about the divisbility of $j$ by $i$ (or rather, lack thereof). – Luke Mathieson Nov 21 '13 at 2:42