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
- $|vwx| \leq n$
- $v$ and $x$ are not both empty: $|vx| \geq 1$
- For all natural numbers $i \in \mathbb{N}_0$: $uv^i wx^i y \in L$
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:
- To show that a language is context-free, create a nondetermenistic pushdown automaton
- To show that a language is not context free, assume it is context free and show that there for all words of minimum length $n$ there can't be any decomposition with the respective properties.
- To show that a language is regular, create a DFA
- To show that a language is not regular, assume it is regular and use the pumping lemma for regular languages to show that for all world of minimum length there is no decomposition with the respective properties.
- You really need to be careful with the quantifiers ($\forall, \exists, \dots$) in the pumping lemma. It is important to understand that the pumping lemma is not an if is only if condition
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$.
Best Answer
The pumping lemma for CFLs says, very roughly, that all sufficiently long strings in a context-free language can be pumped, and when pumped, the resulting strings will always belong to that language.
In symbols, for every long string in a CFL, there's a way to decompose it into the form $\mathsf{uvwxy}$ with certain constraints on what $\mathsf{u,v,w,x,y}$ are, such that $\mathsf{uv}^k\mathsf{wx}^k\mathsf{y}$ is always part of the language for any $k\geq 0$.
To prove that a language is not CFL, you generally argue "Suppose this language is context-free such that strings longer than $N$ are sufficiently long. Here I've made a carefully-constructed string longer than $N$. This means it can be decomposed into the appropriate form, obeying all the constraints. But look—no matter how it is decomposed, I can pump it to produce a string not in the language. This is a contradiction, so the language is not actually context-free."
Your argument says, roughly "What if I decompose the string into the required form $\mathsf{uvwxy}$ then pump it down so that the resulting string doesn't have that pumpable form (because it's become too short)?" But that's not actually a problem—sometimes if you pump down a sufficiently long string, you'll get a string that is too short to be pumpable.
The argument should be "What if I decompose the string into the required form $\mathsf{uvwxy}$ then pump it down so that it isn't in the language anymore?" To use the pumping lemma, the evidence you're looking for is whether your starting string (in the correct form) can be pumped to produce strings that aren't in the language.
Consider the language $\{\mathtt{a}\mathtt{b}^n\mathtt{c}^n\mathtt{a} : n \geq 0\}$. It's context-free. Still, you can take a string like $\mathtt{a}\mathtt{b}^N\mathtt{c}^N\mathtt{a}$ (which is pumpable) and pump it down to make a string like $\mathtt{a}\mathtt{a}$ which isn't pumpable—you can't find a pumpable decomposition where $|\mathsf{vx}|\geq 1$. Still, the language is context-free—turning a pumpable string into a string that is too short to pump doesn't prove anything about being context-free.