Is $L_1$ context free language?

Question

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

$L_1= \left \{ a^m b^mca^nb^m \mid m,n \geq 0 \right \}$

$L_2=\left \{ a^i b^j c^k \mid i,j,k \geq 0 \right \}$

Then L is

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

---

I tried to solve $:$

$L_1 = {c, abcb, abcab, aabbcbb, ...}$

$L_2 = {ϵ, a, b, c, ab, ac, bc, abc, ...}$

So, $L_1 ∩ L_2 = {c}$ , which is Regular.

---

Is $L_1$ context free language and is my explanation correct ?

Answer 1

Yes the result is correct but you don't really say why.

If $s \in L_1$ then $s$ contains a $c$. If also $s \in L_2$ then $s = a^ib^jc^k$ so $k$ has to be $ > 0$ (in fact $k$ has to be $1$) and $s$ ends in a $c$. Because $s \in L_1$, $s=a^mb^mca^nb^m$, so $n = m = 0$ if $s$ is to end in $c$. But then $s = c$.

And clearly $c \in L_1 \cap L_2$.

So $L = L_1 \cap L_2 = \{c\}$.

Thus $L$ is regular, so only 2. is true.