I am trying to use the pumping lemma to show this language is not context free: $L = a^nb^{n+1}c^{2n} : n \ge 0$

So I took $z = a^mb^{m+1}c^{2m}$ where $|z| = 4m+1 > m$. We can decompose $z = a^mb^{m+1}c^{2m}$ to $z = uvwxy$ for $|vwx| \le m$ and $|vx| \ge 1$.

I am confused about what cases to consider to show this is not context free?

| cite | improve this question | | | | |
  • 1
    $\begingroup$ You should revisit how the Pumping lemma works. Hint: Can you prove that $a^nb^nc^n$ is not context-free? $\endgroup$ – Raphael Apr 10 '14 at 7:34

The idea is to look where the portion $vwx$ of $z$ can be in the string. Since the length of $vwx$ is restricted it makes it so there are not too many cases to consider. First is to consider when $vwx$ will be entirely in one letter. So it may be entirely in $a$, $b$ or $c$. So when you pump up or down you will only be affecting that portion. Then it is possible for it to span over two letters but not all three. If $v$ or $x$ is itself across two letters then pumping up will create an equal amount of letters but will be out of order. Another case is if $v$ is only $a$ and $x$ is only $b$ or similarly for $b$ and $c$. Try coming up with the contradictions for all these cases.

| cite | improve this answer | | | | |

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.