Asked By : user5507
Answered By : Ran G.
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
- |vxy| ≤ p,
- |vy| ≥ 1, and
- 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