Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

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 need some help with the following question:

One of the languages

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

is context-free and the other is not. Build a context-free grammar for the one that is. For the other one provide a proof that it is not regular, or that it is not context-free.

How do I approach this problem ? I think that L2 is context-free because no comparisions are made. L1 is not context-free.

Thanks in advance

share|cite|improve this question
up vote 3 down vote accepted

You are actually wrong. I'll give you a hint for the grammar of $L_1$. Rewrite it as $a^p b^r b^q c^{s-t} c^t d^t d^q e^r e^p$. Although I have no idea how the case $s = 0, q = 0$ (thus $q+t < 0$) is supposed to work.

For $L_2$ there is an implicit comparison $r \leq q+r$. Take $p = q = 0$ so that the string is $b^rc^sd^re^s$. You should be able to apply the lemma here easily.

share|cite|improve this answer

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.