enter image description here

If you need some context-: https://www.andrew.cmu.edu/user/ko/pdfs/lecture-11.pdf around page 7.

Case 1-: Say vxy contains ab

So when I pump v and y, what will get pumped? And how the result would be. I can understand the case for when vxy is all a's, all b's or all c's.

Case 2-: Say vxy contains bc

When I pump v and y, what happens? Help me visualize this.

My try-:

I will take case 1.

take i=2 then

We let

$u=a^{n-k} $

$v=a^k $


y=$b^l$ k+l<=n

z=$b^{n-l} c^n$

Now I find $u v^2 x y^2 z$=? whwich gives $a^{n+k} b^{n+l} c^n$ which is obviously not in L. Am I right here?


1 Answer 1


I answer for the case 1, the case 2 is similar.

Since $vxy\in a^*b^*$, and $vy\neq \varepsilon$, that means that $v$ and/or $y$ contains at least one $a$ or at least one $b$, and no $c$. That means that $uxz$ (pumping can also mean considering $uv^0xy^0z$) contains strictly more $c$'s than either $a$'s or $b$'s (or both), so $uxz\notin \{a^nb^nc^n\mid n\in\mathbb{N}\}$.


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.