# Is $L_1$ context free language?

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 ?

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.

• how we recognize $L_1$ in single stack ? – 1 0 Oct 16 '15 at 8:45
• then any number of $b$s, no , it should be equal $a^m$ or $b^m$ ? – 1 0 Oct 16 '15 at 9:03
• Anyway that's a separate question. This one has a correct answer now :) – BrianO Oct 16 '15 at 9:17
• – 1 0 Oct 16 '15 at 9:21
• OK good (other question, I mean) – BrianO Oct 16 '15 at 9:29