HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaMinor

why does ${a^nb^n}$ fit the pumping lemma for context-free languages?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
whythefreelanguagespumpingfordoeslemmacontextfit

Problem

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

Solution

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.

Context

StackExchange Computer Science Q#14994, answer score: 3

Revisions (0)

No revisions yet.