[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 $pge2$.$^3$ The lemma says, that for any long enough $s$ string in $L$ (let’s take $s=a^mb^m$ with $mge 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|=2ge1$. 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^nepsilon b^{n}b^{m-1}$$ indeed! for any $nge 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