0
$\begingroup$

$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 ?

$\endgroup$
  • $\begingroup$ Sorry, I made a mistake. I edited $\endgroup$ – user220688 Apr 20 '15 at 16:54
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ I posted below, $\endgroup$ – user220688 Apr 21 '15 at 18:15
0
$\begingroup$

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$

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

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 $

$\endgroup$

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.