edited by
3,508 views
28 votes
28 votes

Let $L$ be a given context-free language over the alphabet $\left\{a, b\right\}$. Construct $L_{1},L_{2}$ as follows. Let $L_{1}= L - \left\{xyx\mid x, y \in \left\{a, b\right\}^*\right\}$, and $L_{2} = L \cdot L$. Then,

  1. Both $L_{1}$ and $L_{2}$ are regular.
  2. Both $L_{1}$ and $L_{2}$ are context free but not necessarily regular.
  3. $L_{1}$ is regular and $L_{2}$ is context free.
  4. $L_{1}$ and $L_{2}$ both may not be context free.
  5. $L_{1}$ is regular but $L_{2}$ may not be context free.
edited by

2 Answers

Best answer
54 votes
54 votes

$L$ is a context free language over $\{a,b\}$
$L_1 = L - \{xyx \mid x,y \in \{a,b\}^* \}$    

      $= L - \{ \text{all strings over} \{a,b\} \}$    [ Note: all strings can be generated from y by putting $x= \epsilon$]

      $= L - (a+b)^* = \{\}$ , empty set.    [Note : $L_1 - L_2 = \{ \text{string in $L_1$ but not in L2 }\}$ ]

So , $L_1$ is a Regular Language. 

$L$ is a context free language over $\{a,b\}$ 

$L_2 = L \cdot L$
Context free languages are closed under Concatenation. 

So, $L_2$ is Context Free Language.

Option C is correct.

edited by
9 votes
9 votes

L1 =  CFL - (x+y)* = ∅  Which is Regular.

L2 = CFL . CFL = CFL

Since CFL Is  Closed Under Concatination.

C Is Answer.

edited by
Answer:

Related questions