1
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.