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


3 Answers 3


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

  • 3
    $\begingroup$ You can choose $n$ larger than the pumping length, and then you are guaranteed that $|vwx| < n$. $\endgroup$ Apr 28, 2015 at 18:06
  • 1
    $\begingroup$ You are right. My bad. $\endgroup$ Apr 28, 2015 at 21:41
  • $\begingroup$ Very good @RenatoSanhueza, your interest will be considered. $\endgroup$ Apr 29, 2015 at 23:30

it is CFL. consider this CFG

S --> X | Y

X --> aXb | aX | a

Y --> aYb | Yb | b

  • 5
    $\begingroup$ 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). $\endgroup$ Nov 21, 2013 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.