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$
  • $\begingroup$ contextfree rule for building this grammar: <S> = a<S>b $\endgroup$ – Sim Oct 10 '13 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$ – user2226106 Oct 10 '13 at 20:02
2
$\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="", u=a^(m-1), z=b^(m-1).

You can definitely pump it as much as you want. In other words, you take a string such as aaaaaabbbbb, then you pick the two middle letters: aaaa ab bbbb. Then you pump them: aaaa aaabbb bbbb. Still in the language.

$\endgroup$
  • $\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$ – user2226106 Oct 10 '13 at 20:23
  • $\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$ – Mark Dominus Oct 10 '13 at 20:49
  • 1
    $\begingroup$ Note: you can use LaTeX math in posts and comments, just type $...$. $\endgroup$ – Raphael Oct 11 '13 at 7:31
  • 1
    $\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 Sep 10 '14 at 13:02

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.