Are these languages context free or not?

Question

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!

Answer 1

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.

Answer 2

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.

Answer 3

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.