2
$\begingroup$

I want to show that the following language is not context-free:

$$\{a^nb^m\mid0\leq n\leq m^2\}$$

I tried the word $w=a^kb^k$, but it does not work, because I can't show that for every possible partition $w=uvxyz$ (with the conditions of the context-free-pumping-lemma), an $i$ exists that the number of $a$'s are more than $k^2$. The problem is, that the number of $b$'s is growing as well.

Every word I tried seems to have this problem. Do you know a word, which might work?

Thanks in advance.

| cite | improve this question | | | | |
$\endgroup$
  • $\begingroup$ Are you familiar with Parikh's theorem? $\endgroup$ – Noah Schweber Dec 9 '15 at 7:04
  • $\begingroup$ No, unfortunately I am not. $\endgroup$ – ChamDao Dec 9 '15 at 7:06
1
$\begingroup$

If $p$ is the pumping length, start with $w=a^{p^2}b^p$. Suppose that $w=uvxyz$ is such that $|vxy|\le p$, $|vy|\ge 1$, and $uv^kxy^kz\in L$ for each $k\ge 0$. Clearly we cannot have $vxy=a^r$ for some $r$, since we can then pump up to get too many $a$s. We also cannot have $vxy=b^r$ for some $r$, since in that case pumping down (i.e., setting $k=0$) takes us out of $L$. It’s also clear that neither $v$ nor $y$ can contain both letters, so we must have $v=a^r$ and $y=b^s$ for some $r,s>0$. If $r>s$, pumping up will take us out of $L$, so $r\le s$. But then pumping down will take us out of $L$, since

$$p^2-r\ge p^2-s>(p-s)^2\;.$$

You’ll have to do a little work to prove the last inequality, but it’s not too hard to show.

| cite | improve this answer | | | | |
$\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.