3
$\begingroup$

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

$\endgroup$
5
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

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

it is CFL. consider this CFG

S --> X | Y

X --> aXb | aX | a

Y --> aYb | Yb | b

$\endgroup$
  • 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$ – Luke Mathieson Nov 21 '13 at 2:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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