Pumping lemma for CFG doubt

Question

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?

Answer 1

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 want to prove that a language is 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.

Answer 2

It's wrong to take $u$ to be $\epsilon$. Pumping lemma for regular languages says that the substring to pump will be somewhere near the beginning of the string. Pumping lemma for context free languages says no such thing. In general, neither pumping lemma lets you make many assumptions about what to pump. In the case of $a^nb^n$, the substring to pump will always be in the middle.