1
$\begingroup$

I am working on a pumping lemma question and trying to prove that the following is not context-free, but I can't finish the proof. The language is

$$L = \{ a^n b^m \mid n \leq m^2 \}$$

Assume Demon picks $p$ and I choose $s = a^{p^2}b^p$ and $s = uvwxy$ such that $p \geq |vwx|$.

The first case is $vwx = b^j$. If we choose $i = 0$ everything is ok and the relationship isn't right.

The second case is $vwx = a^j$. If we choose $i = 2$ every thing is ok.

I get stuck when $vwx = a^j b^k$. How can I finish the proof in this case?

Did I choose the right string? I repeated them for $s = a^{p}b^p$ but it didn't work.

$\endgroup$
3
  • 1
    $\begingroup$ Is the condition $n \le m^2$ or $n \ge m^2$? $\endgroup$ May 14 at 16:54
  • $\begingroup$ @YuvalFilmus I think it is indeed $n\leq m^2$, since it is coherent with the first two cases: removing $b$'s prove the word is not in $L$, and it is the same when adding $a$'s. $\endgroup$
    – Nathaniel
    May 14 at 17:58
  • $\begingroup$ @YuvalFilmus it's n≤m2. question edited. $\endgroup$
    – hermi
    May 15 at 7:31
2
$\begingroup$

When $vwx = a^j b^k$, there are two possibilities:

  • $v$ contains both $a$s and $b$s, or $x$ contains both $a$s and $b$s. In this case $uv^2wx^2y \notin a^*b^*$, and in particular $uv^2wx^2y \notin L$.
  • $v = a^s$ and $x = b^t$, where $s,t>0$ and $s+t \leq p$ (since $|vwx| \leq p$). In this case, $uv^0wx^0y = a^{p^2-s}b^{p-t}$, and so $p^2 - s \leq (p-t)^2 \leq (p-1)^2$, which translates to $s \geq 2p-1$, which is impossible, since $s \leq p-1$.
$\endgroup$
9
  • $\begingroup$ I don't understand the first one. We are not sure about the amounts of a or b in v and x. $\endgroup$
    – hermi
    May 18 at 6:42
  • $\begingroup$ They don't matter. What matters is that after pumping, you're not of the form $a^*b^*$. $\endgroup$ May 18 at 6:46
  • $\begingroup$ for example v = a and x = abbb when i = 2 uv^2wx^2y is a member of language . $\endgroup$
    – hermi
    May 18 at 6:48
  • $\begingroup$ What word do you start with? And what does $uv^2wx^2y$ look like? $\endgroup$ May 18 at 6:49
  • $\begingroup$ Can you give an example? I say it's not a form of {a^nb^m∣n≤m2} $\endgroup$
    – hermi
    May 18 at 6:50

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.