Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have a problem finding the right string to pump for the following language:

$$L_1 = \{a^{p+q}b^rc^sd^{q+r}e^s \mid p, q, r, s \ge 0\}$$

Which string should I choose to pump? The problem is that I don't know how to handle the fact that I have $p+q$ and $q+r$?

Can I choose: $$Z = a^{2n}b^nc^nd^{2n}e^s$$

Thanks in advance.

share|cite|improve this question
You should prefer using latex instead of images. That makes it searchable and editable. You can click on edit of various questions to see examples. – Paresh Jan 4 '13 at 9:48
I assume you refer to the regular pumping lemma? – A.Schulz Jan 4 '13 at 9:54
up vote 2 down vote accepted

If $k$ is the pump length from the regular pumping lemma choose $w=c^ke^k$. Clearly, $w\in L_1$, but if you pump you have to change the number of $c$'s while leaving the $e$'s unaltered. Hence after pumping the word is no longer a member of $L_1$.

share|cite|improve this answer
Hi ! Than you very much, the question was rather simple but I didn't noticed that p,q,r can be 0 :D – mrjasmin Jan 4 '13 at 10:00

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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