# Are these languages context free or not?

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) \}$

-
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 cs.stackexchange.com 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.

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

-

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.

-