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


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.


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.