Prove language is not context free with pumping lemma

Question

$$L=\big\{a^{3k}b^{2k}c^k\in\{a,b,c\}^* | k>= 0\big\}$$

I'm trying to use the pumping lemma to prove this language is not context free.

so far I have...

$p=$ Pumping lemma

$S = a^{3p}b^{2p}c^p$

$S = uvwxy$

$|vwx| <= p$

$|vx| >= 1$

$u=a^{3p}b^{p}$

$v = b^i$

$w=b^j$

$x = b^{p-j-i}$

$y=c^p$

Is this the right way to be going? what do I do next?

Answer 1

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.

1. $vwx=a^n$ for some $n$ such that $1\le n\le p$.
2. $vwx=b^n$ for some $n$ such that $1\le n\le p$.
3. $vwx=c^n$ for some $n$ such that $1\le n\le p$.
4. $vwx=a^mb^n$ for some $m$ and $n$ such that $1\le m+n\le p$.
5. $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$.