1
$\begingroup$

$$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?

$\endgroup$
2
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Do I have to show a contradiction in each of the cases you mention? Isn't finding a contradiction in one of them enough to prove it is not context free? $\endgroup$ – sam Dec 6 '14 at 12:07
  • $\begingroup$ No it isn't, because in the pumping lemma it does not tell you where the subwords $v,w,x$ start or end, so you have to consider all 5 cases to get a contradiction (if you could not get a contradiction in one of the cases, then this decomposition into subwords would work and so the language would not be non-context-free a priori). $\endgroup$ – MHS Dec 6 '14 at 13:58
  • $\begingroup$ How do I find the different cases / know when I have them all? $\endgroup$ – sam Dec 6 '14 at 15:38
  • $\begingroup$ @sam: Ask yourself what a substring of $s$ whose length is $\le p$ can look like. In this case you get the five possibilities that I listed. $\endgroup$ – Brian M. Scott Dec 6 '14 at 20:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.