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.

  • $\begingroup$ 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. $\endgroup$ – Paresh Jan 4 '13 at 9:48
  • $\begingroup$ I assume you refer to the regular pumping lemma? $\endgroup$ – A.Schulz Jan 4 '13 at 9:54

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

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

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.