3
$\begingroup$

I am writing somthing about Ppumping Lemma. I know that the language $L = \{ a^nb^n| n ≥ 0 \}$ is context-free. But I don't understand how this language satisfies the conditions of pumping lemma (for context-free languages) ?

if we pick the string $s = a^pb^p, |s| > p , |vxy| < p \land |vy| > 0$.

it seems it will be out of the language when we pump it (pump up or down) or there is something I'm missing.

Any explanation would help.

Edit: I am applying pumping lemma to a^nb^n and it fails to stay in the language for all cases. So, why is it Context free?

$\endgroup$
2
  • $\begingroup$ contextfree rule for building this grammar: <S> = a<S>b $\endgroup$
    – Sim
    Commented Oct 10, 2013 at 20:01
  • 1
    $\begingroup$ yes I know that but I just wanted to see that this language satisfies the conditions of the pumping lemma. @Sim $\endgroup$ Commented Oct 10, 2013 at 20:02

1 Answer 1

3
$\begingroup$

This language satisfies the conditions of the pumping lemma. (By the way, your question title is wrong: you are not asking why it is context-free; you are asking why it satisfies the conditions of the lemma, which it does.)

Take the string $s=a^mb^m$ and assume $m>0$. Don’t use $p$ or $n$; otherwise it is confusing, because those letters are used in the lemma. Now let $v=a$, $y=b$, $x=\epsilon$ (the empty string), $u=a^{m-1}$, and $z=b^{m-1}$.

You can definitely pump it as much as you want. In other words, you take a string such as $aaaaabbbbb$, then you pick the two middle letters: $aaaa\mathbf{ab}bbbb$. Then you pump them: $aaaa\mathbf{aaabbb}bbbb$ — still in the language.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer but if I pump up aaaabbbb, while string is middle ab, first pumping produces "aaaa abab aaaa" and it is out of order now. @Sergey Orshanskiy $\endgroup$ Commented Oct 10, 2013 at 20:23
  • 1
    $\begingroup$ No, because the $\def\a{{\mathtt a}}\def\b{{\mathtt b}}\a$ part of the $\a\b$ is in string $v$, and the $\b$ part is in string $y$, and in between is the string $x$, which is empty. $v$ and $y$ get pumped separately, so pumping $\a\b$ gives us $\a^n\b^n$, not $(\a\b)^n$. $\endgroup$ Commented Oct 10, 2013 at 20:49
  • 2
    $\begingroup$ Sergey , i think that its not enough just to find few cases that you cant pump the string...for ANY choice of v ,x and y you have to show that you cant pump the string...so in our case like Mark mentioned there is a choice of v,x,y that you can pump it (v=a,y=b,x="") so game over... $\endgroup$
    – user21619
    Commented Sep 10, 2014 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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