gotchaMinor
why does ${a^nb^n}$ fit the pumping lemma for context-free languages?
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?
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.
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.