[Math] Intersection of two languages

automatacontext-free-grammarformal-languagesregular expressionsregular-language

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 ?

Best Answer

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.

Related Question