You’ve taken $p$ to be the pumping length (not pumping lemma!), and you’ve decided to look at that word $s=a^{3p}b^{2p}c^p$; that’s fine. The pumping lemma tells you that $s$ can be decomposed as $s=uvwxy$ in such a way that $|vwx|\le p$, $|vx|\ge 1$, and $uv^kwx^ky\in L$ for each $k\ge 0$. However, it does not say that you get to pick $u$: $vwx$ could be any substring of $s$ whose length is between $1$ and $p$, inclusive. You have to show that no matter which such substring $vwx$ is, and no matter how it splits among $v,w$, and $x$ (provided, of course, that $|vx|\ge 1$), there is some $k\ge 0$ such that $uv^kwx^ky$ actually isn’t in $L$; that’s how you get your contradiction proving that $L$ cannot in fact be context-free.
You have several different cases to consider.
- $vwx=a^n$ for some $n$ such that $1\le n\le p$.
- $vwx=b^n$ for some $n$ such that $1\le n\le p$.
- $vwx=c^n$ for some $n$ such that $1\le n\le p$.
- $vwx=a^mb^n$ for some $m$ and $n$ such that $1\le m+n\le p$.
- $vwx=b^mc^n$ for some $m$ and $n$ such that $1\le m+n\le p$.
In the first three cases you should be able to explain quite easily why $k=1$ is the only value of $k\ge 0$ such that $uv^kwx^ky\in L$: changing it to anything else will take you out of $L$ — which of course would not be possible if $L$ really were context-free. The same thing is true in the last two cases, though you may have to think a little more to see why and to explain it clearly.
Finally, you will have to show that these really are the only five possibilities for $vwx$.
For cases 9 through 13 :
"This string" is $uv^0wx^0y=a^kb^ks$. If "this string" is in $L$, it must have even length, so $s$ has even length too, say $2t$ for some integer $t$. The total length of "this string" is then $k+k+2t=2(k+t)$. Since $v$ and $x$ are not both empty, $uvwxy$ has length strictly greater than $uv^0wx^0y$, so "this string" has length $<4k$, and we deduce that $t<k$.
The first half of "this string" is made of the first $k+t$ symbols, so the first half is $a^kb^t$. As you can see, this first half starts with an $a$.
The second half of "this string" is made of the last $k+t$ symbols, so the second half is $b^{k-t}s$. As you can see, this second half starts with a $b$.
For cases 6,7,8 :
In this case, "this string" is $uv^0wx^0y=a^ksb^k$. As above, $s$ must have even length, say $2t$ for some integer $t$. The total length of "this string" is then $k+k+2t=2(k+t)$. Note that $t<k$. Denote by $s_1,s_2,\ldots,s_{2t}$ the symbols in $s$.
The first half of "this string" is made of the first $k+t$ symbols, so the first half is $a^ks_1s_2\ldots s_t$. As you can see, this first half starts with $a^k$.
The second half of "this string" is made of the last $k+t$ symbols, so the second half is $s_{t+1}s_{t+2}\ldots s_{2t}b^k$. As you can see, this second half ends with $b^k$.
If "this string" is in $L$, the first half and the second half are in fact the same string, called $r$ in the text. Then $r$ must both start with $a^k$ and end with $b^k$, which forces $r$ to have length $\geq 2k$. This means that $uv^0wx^0y=rr$ has length $\geq 4k$. Since $v$ and $x$ are not both empty, $uvwxy$ has length strictly greater than $uv^0wx^0y$, and we deduce $4k>4k$ which is absurd.
Hope this helps !
Best Answer
The Pumping Lemma says, that if $L$ is context-free, there exists $n \in \mathbb{N}$, such that for every word which is longer than $n$ there is a decomposition with
So let's see we can find a word from $L = \{a^n b^n\ | n \geq 0\}$ that fulfills these conditions. If we can show that, that would not mean however that $L$ is context-free!
So let $L$ be context-free. Choose $n = 2$. Let $z = a^k b^k \in Z$ with $|z| \geq n$, so $2k \geq n$. Then you can choose the following decomposition (for example):
With $a^k = a^{k-1} a^1$, $b^k = b^1 b^{k-1}$ choose $u= a^{k-1}$, $y = b^{k-1}$ and $v = a$, $x = b$, $w = \varepsilon$. So $|vx| \geq 1$, $|vwx| = 2 \leq n$ Then
$$z = u v^i wx^i y = a^{k-1} a^i b^i b^{k-1} $$
which has exactly as many $a$'s as $b$'s.
To show that $L$ is context free, you can create a nondetermenistic pushdown automaton. Once you've found one you have shown that $L$ is context-free.
Note that you can always find a word in any context-free or regular language and decompose it so that the word does not fulfill the requirements. But that doesn't say anything. $L$ is not context-free if you can show that for every word with length of at least $n$, there is no decomposition whatsoever of this kind - not that you've found one decomposition that doesn't work.
Conclusion: