0
$\begingroup$

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 ?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Strings of $L=\{c,abc,aabbc,aaabbbc,......,a^mb^mc |m≥0\}$ , Is not correct ? $\endgroup$ – 1 0 Nov 15 '15 at 7:21
  • $\begingroup$ 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$. $\endgroup$ – BrianO Nov 15 '15 at 7:26
  • $\begingroup$ Yes, I got it . Thank you :) $\endgroup$ – 1 0 Nov 15 '15 at 7:27
  • $\begingroup$ Good :) You're welcome. $\endgroup$ – BrianO Nov 15 '15 at 7:28
1
$\begingroup$

$L=L_1\cap L_2=\left \{ c \right \}$, so $L$ is regular.

$\endgroup$

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.