# Intersection of two languages

Let $L=L_1∩L_2$, where $L_1$ and $L_2$ are languages as defined below:

$L_1=\{a^mb^mca^nb^m∣m,n≥0\}$

$L_2=\{a^ib^jc^k∣i,j,k≥0\}$

Then $L$ is

1. Not recursive
2. Regular
3. Context free but not regular
4. Recursively enumerable but not context free.

My attempt :

$L_1$ is CSL(context sensitive language) and $L_2$ is regular . The intersection of both languages should be CFL(context free language), and

$L= \{a^mb^mc∣m≥0\}$

Can you explain little bit please ?

If $s\in L$, then $s = a^ib^jc^k$ for some $i,j,k\ge 0$, but also $s = a^mb^mca^nb^m$ for some $m, n\ge 0$. So we must have $k = 1$, and $n=0$. Furthermore, we must have $i=j=m$. So $s = a^mb^mc = a^mb^mcb^m$. But then we have to have $m = 0$. So $s = c$. Thus $L = \{c\}$ is regular.
• Strings of $L=\{c,abc,aabbc,aaabbbc,......,a^mb^mc |m≥0\}$ , Is not correct ? – ً ً Nov 15 '15 at 7:21
• If $abc\in L$ then $abc\in L_2$, so $abc = a^mb^mca^nb^m$ for some n. But then $n$ has to 0 as there are no $a$s after the $c$, ... But this is impossible: there are no $b$s after the $c$ either, so $m=0$... but then supposedly $abc= a^0b^0cb^0 = c$. The number of $b$s after the $c$ in $L_2$ is the same as the number of $a$s and of $b$s *before* the $c$. – BrianO Nov 15 '15 at 7:26
$L=L_1\cap L_2=\left \{ c \right \}$, so $L$ is regular.