Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. 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
  1. $L_1=\{a^nb^mc^nd^m \mid m,n >0\}$
  2. $L_2=\{a^nb^mc^md^n \mid m,n >0 \}$
  3. $L_3=\{a^mb^n \mid m+n\text{ is a prime number}\}$
  4. $L_4=\{a^mb^n \mid n=m^2\}$
  5. $L_5=\big\{ww^R\#ww^R \mid w \in \{a,b\}^* \big\}$
  6. $L_6=\big\{wuw^R \mid |w|=|u|, w,u \in \{a,b\}^* \big\}$
  7. $L_7=\big\{wu \mid |w|=|u|, w,u \in\{a,b\}^*\big\}$
  8. $L_8=\{a^mb^nc^k \mid k \le \min(m,n) \}$
  9. $L_9=\{a^mb^nc^k \mid k \le \max(m,n) \}$

thanks in advance!

share|cite|improve this question
Welcome to MSE! Can you format your items using MathJax to make them more readable? Regards! – Amzoti Jan 12 '13 at 0:42
That is way too much to put in a single question; please bread this into several questions. It would also be a very good idea to give some indication of what ideas you’ve had towards answering at least some of them. – Brian M. Scott Jan 12 '13 at 0:47
May be is more fit for this question? – Mohan Jan 12 '13 at 1:35
First try creating a context-free grammar for these languages and if you are unable to do so ,use pummping lemma to prove they are not context free. – Mohan Jan 12 '13 at 1:37
@Mohan: We deal with this kind of question quite often at MSE. – Brian M. Scott Jan 12 '13 at 1:41

A few HINTS:

  • It’s extremely easy to write down a context-free grammar that generates $L_7$.

  • It’s almost as easy to come up with a context-free grammar that generates $L_2$: design it to generate the $a$’s and $d$’s simultaneously first, and then the $b$’s and $c$’s simultaneously.

  • The Bar-Hillel pumping lemma will settle $L_1,L_5$, and $L_7$ very easily, and $L_3$ and $L_4$ with just a bit more work.

Now that you at least have some pointers in the right direction, try to make some progress on a few of these, and then ask more specific questions.

share|cite|improve this answer
What about $L_8$ and $L_9$ ? :) – Yoni Hassin Jan 14 '13 at 17:21

It is a long question, so, I´ll give you a quickly anwser: you must use the Pumping Lemma for Context Free Languages (CFL). In Wikipedia you can read more about it. Also here you find examples of how to prove that a language is not CFL.

share|cite|improve this answer

1) We can prove that $L_1$ doesn't satisfy the conditions of pumping lemma

Let the pumping length be $n$. Now consider the string $S=a^nb^nc^nd^n$.We must decompose $S$ in to $uvxyz$ such that it satisfies conditions of pumping lemma. So, what can be $u,v,x,y$ and $z$ be equal to so that conditions of pumping lemma are satified? We know that $|vxy| \leq n$. Check the following cases

1.$vxy$ can't consist only of $a$'s and $b$'s.Because if $v=a^i$ and $u=b^k$, $a^{n+i}b^{n+k}c^nd^n \notin L$.

2.Using a similar reasoning to prove that $vxy$ can't consist of $b$'s and $c$'s.

3.$vxy$ also can't consist of $c$'s and $d$'s in a similar way.

So, we have have proved that the string $S$ can't be decomposed in to $uvxyz$ such that it satisfies the conditions of pumping lemma. That means $L$ is not context free.

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.