Take the 2-minute tour ×
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.

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

1 Answer 1

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

 
discard

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.