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
I’ll walk you through the argument.
Suppose that $L=\{ba^nbc^n:n\ge 1\}$ is regular. Then the pumping lemma for regular languages says that it has a pumping length $p$ such that if $w$ is any word of $L$ whose length is at least $p$ (i.e., such that $|w|\ge p$), then $w$ can be decomposed as $w=xyz$ in such a way that $|xy|\le p$, $|y|\ge 1$, and $xy^kz\in L$ for every $k\ge 0$. In order to use the pumping lemma to show that $L$ is not in fact regular, we must find a word $w$ for which this yields some contradiction. Finding such a $w$ is largely a matter of practice and experience with similar problems.
Here we can take $w=ba^pbc^p$. No matter how we split this as $w=xyz$, if $|xy|\le p$, then the $xy$ part is some initial segment of the first $p$ letters of $w$, i.e., of $ba^{p-1}$. There are now two possibilities that have to be distinguished.
- If $|x|\ge 1$, then the initial $b$ of $w$ is part of $x$, and $y=a^r$ for some $r$ such that $1\le r\le p-1$.
If this is the case, then $x=ba^s$ for some $s\ge 0$ such that $r+s\le p-1$, and $z=a^{p-r-s}bc^p$; why? Then for any $k\ge 0$ we have
$$xy^kz=ba^sa^{kr}a^{p-r-s}c^p=ba^{p-r+(k-1)r}bc^p\;.$$
You can easily check that this is in $L$ if and only if $k=1$. If $k=0$, the block of $a$s is shorter than the block of $c$s, and if $k>1$, the block of $a$s is longer than the block of $c$s; in both cases the word is not in $L$.
- If $x$ is empty, then $y=ba^r$ for some $r\le p-1$.
In this case $z=a^{p-r}bc^p$, and
$$xy^2z=y^2z=ba^rba^pbc^p\;,$$
which is plainly not in $L$. This is sufficient, but we can go further and note that in fact $xy^kz\in L$ if and only if $k=1$, so that we just have the original $w$: $xy^kz$ has $k+1$ $b$s, while every member of $L$ has exactly two $b$s.
Best Answer
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.
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$.