Virtual Gate Test Series: Theory Of Computation - Languages

Question

Let $L$ be a given context-free language over the alphabet $\{a, b\}$. Construct $L1, L2$ as follows.
Let $L1 = L − \{xyx \mid x, y \in \{a, b\}^*\}$,
and $L2 = L·L$. Then,

1. Both $L1$ and $L2$ are regular.
2. Both $L1$ and $L2$ are context-free but not necessarily regular.
3. $L1$ is regular and $L2$ is context-free.
4. $L1$ and $L2$ both may not be context-free.

Comments

I think B

L1 is cfl as we're taking set difference of a rl from a cfl

L2 is also cfl as cfls are closed under concatenation

Answer 1

I am getting $L_1$  regular and $L_2$ CFL.

$\Rightarrow M=\left \{ xyx |x,y\epsilon \left ( a,b \right )^*\right \}=(a+b)^*$

$L_1=L-M=L\cap M^{'}=L \cap \phi=\phi$ which is regular

$L_2$is CFL as CFL are closed under concatenation and nothing is given about $L$

Comments

In M shouldn't we need to store the first string x which has to be repeated after y?

---

but the strings generated from (a+b)* might not always be of xyx form  @sourav.  sir

---

@ Utsav09

see this https://gatecse.in/identify-the-class-of-a-given-language/

Particularly example $5$

Answer 2

option c

Comments

L=anbn    and take x=y=epsilon

then L1=L which is CFL

????