[Solved]: Pumping lemma for CFG doubt

Problem Detail: 

I was looking at the pumping lemma for CFG. I came across the first problem $a^nb^nc^n$ and understood the answer. Then I thought of the problem $a^nb^n$. I know that this is context free and thought of applying it. I came across a weired situation. Someone please tell me where I went wrong.

So our language is $a^nb^n$. Let $m$ be the pumping length. Pumping lemma says that any sufficiently long string can be divided in $uvxyz$, where $v$ and $y$ can be pumped.

we take our string to be $a^mb^m$ and we can split it into $uxvyz$. Also we know that $|vxy|\le m$. Also $u$ can be $\epsilon$. In that case $vxy$ consists only of $a$, since $|vxy|\le m$ and there are $m$, $a$'s. So when we pump $v$ and $y$, the resulting string wont be in the language!

So where I got wrong? Is it wrong to take $u$ is $\epsilon$ and proceed from there?

Asked By : user5507

Answered By : Ran G.

I'm not sure why the answer of Karolis doesn't satisfy you. Let me chew it a bit more for you. First, let's recall what the pumping lemma says (taken form the credible source of Wikipedia):

If a language L is context-free, then there exists some integer p ≥ 1 such that any string s in L with |s| ≥ p (where p is a "pumping length") can be written as

s = uvxyz

with substrings u, v, x, y and z, such that

1. |vxy| ≤ p,
2. |vy| ≥ 1, and
3. uv$^n$xy$^n$z is in L for all n ≥ 0.

Ok, so you say $L=\{a^nb^n \mid n \ge 0\}$ is CF, and thus we can run the Lemma on it. Great. Here I'll show you that the lemma works for it. Say the pumping length is $p\ge2$.$^3$

The lemma says, that for any long enough $s$ string in $L$ (let's take $s=a^mb^m$ with $m\ge p$ as you suggest) we can write it as $uvxyz$ that satisfies some conditions.$^1$

Ok, let's give a try. Let's set $u=a^{m-1}$, $vxy=ab$, $z=b^{m-1}$.

Sanity check: indeed, $uvxyz$ gives $s$. I don't know yet how to split the middle part into $vxy$, but see that condition (1) is satisfied, $|vxy|= 2 \le p$. Now for condition (2), i'll have to get the $vxy$ thing. Let's take $x=\epsilon$, thus $v=a$ and $y=b$. Do we satisfy condition (2)? Yes! $|vy|=2\ge1$. Yey.

Now, it says that no matter what $n$ I take, $uv^nxy^nz$ needs to be a word in the language $L$. Let's see. By the way we picked the substrings, $$ uv^nxy^nz = a^{m-1}a^n\epsilon b^{n}b^{m-1}$$ indeed! for any $n\ge 0$ we pick the word we get is $a^{m+n-1}b^{m+n-1}\in L$.

To conclude, we were able to take any word in $L$, and write it as $uvxyz$ so that the conditions of the lemma hold. This can be done for any language which is context-free (and for some that are not, as well) and we just saw how to do it for $L$.

more questions?

$^{1)}$ This should be emphasized: any word can be written in some way uvxyz etc. It doesn't mean that ALL the possible $uvxyz$ will work. Only one of them needs to work in order to satisfy the lemma.
$^{2)}$ when you prove that a language in not CF, then all the ways $uvxyz$ must be checked. This is because when you negate the lemma, the word "There exists ... that satisfies (1), (2), (3)" negates to "does not exist ... that satisfy" == "for all ... the condition is not satisfied". So to prove $L$ is not-CFG you need to check all possible ways. To show the lemma is satisfies for a CF $L$, you only need to find one.
$^{3)}$ What if $p=1$? Well, it is not. The lemma says that there exists some $p$. It doesn't say what this $p$ is. For our $L$, any $p \ge 2$ works, but $p=1$ doesn't. We need just one such $p$ (i.e., there exists), so taking $p=2$ is enough.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/10873