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 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|improve this question
add comment

1 Answer 1

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|improve this answer
add comment

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.