# prove that language is not free context

$F=\{\,a^ib^j\mid i=kj\text{ for some$k>0$}\,\}$
Prove that this language is not context free.
The only thing that comes to my mind is pumping lemma; Let $p$ be the pumping length. Given $s=a^{pk}b^p =uvxyz$ for some positive $k$. When $v$ or $y$ contains simultaneously $a$ and $b$ then $uv^2xy^2z\notin F$. But I have a problem now. How to continue ?

• Sorry, I made a mistake. I edited – user220688 Apr 20 '15 at 16:54

Hint: Show that $v$ is a string of all $a$ and $y$ is a string of all $b$ (Why?). Then show that the ratio of number of $a$ to number of $b$ in the strings being pumped is precisely the ratio of the length of $v$ to the length of $y$. So this is the only positive $k$ you are able to capture in your language, so you cannot have all $k$ being satisfied in your language.

• I posted below, – user220688 Apr 21 '15 at 18:15

By the pumping lemma, $a^{2p+2}b^{p+1}=uvw$ with $|uv|\le p$ and $|v|>0$ such that $uv^iw\in F$ for all $i\ge 0$. Clearly $v=a^r$ or $v=b^r$ for some $0<r\le p$ as otherwise $uvvw\notin F$. If $v=b^r$, then for $i$ large enough $uv^iw=a^{2p+2}b^{p+1+ri}\notin F$. If $v=a^r$, then $uw=a^{2p+2-r}b^{p+1}\notin F$

• You showed that it is irregular, but question was about context free – user220688 Apr 21 '15 at 17:47

I try use @user2566092 hint:

Show that $v$ is a string of all $a$ and $y$ is a string of all $b$ (Why?)

I explained in my first post that there is no possibility that $v$ or $y$ contains simultaneoulsy $a$ and $b$. So let's suppose that $v$ and $y$ contains only $a$. Then it must be that $|y|+|v|=p$. So let's consider $k=1$ now, $w=a^pb^p\in F$. If we pump down it then $a^0b^p=b^p\notin F$. The situation when $v$ and $y$ contains only $b$ is symetric. Last case is $v$ contains only $a$ and $y$ contains only $b$, as you demand.

I don't agree to the fact that $v$ is string of all $a$ and $y$ is string of all $b$. After all, there is constraint that $|v|+|y|\le p$, but $|v|+|y| = pk+p > p$