TIFR CSE 2014 | Part B | Question: 13

Question

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,

• A. Both $L_{1}$ and $L_{2}$ are regular.
• B. Both $L_{1}$ and $L_{2}$ are context free but not necessarily regular.
• C. $L_{1}$ is regular and $L_{2}$ is context free.
• D. $L_{1}$ and $L_{2}$ both may not be context free.
• E. $L_{1}$ is regular but $L_{2}$ may not be context free.

Comments

Since x,y both belong to (a+b)*

You can imagine y to have any length. So it would actually match all strings starting and ending in the same symbol.

Ex: ababba belongs to the language because in this case x = a and y = babb

Since there is no restriction on x's length, x can even be $\epsilon$

The regular expression for such a language would be

= a(a+b)*a + b(a+b)*b + $\epsilon$(a+b)*$\epsilon$

= (a+b)*

---

no restriction on length, i.e I can choose any length for x & y

abbabbaab, here if x = ab then is it in the language??

---

Yes. Only condition is x and y should belong to (a+b)*

Answer 1

$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.

Comments

@Praveen Saini sir

Suppose L=aⁿbⁿ

L2=L.L = aⁿb^{n .} aⁿbⁿ  

So after concatination it will be CFL ...can u tell me what changes has been happen over here

i.e what L2 contains ??

---

$$\begin{align*} & L.L = {\color{red}{\left ( a^n.b^n \right )}}.{\color{blue}{\left ( a^k.b^k \right )}} \\ &L.L = {\color{red}{\left ( ab,aabb,aaabbb...... \right )}}.{\color{blue}{\left ( ab,aabb,aaabbb...... \right )}} \\ &L.L = \left \{ {\color{red}{ab}}{\color{blue}{ab}},{\color{red}{ab}}{\color{blue}{aabb}},{\color{red}{ab}}{\color{blue}{aaabbb}},{\color{red}{aabb}}{\color{blue}{ab}} ....\text{etc..} \right \} \end{align*}$$

---

no relation between n and k

---

@Debashish Deka 

I know if they are from differnet Language like

L1=aⁿbⁿ  and L2 =aⁿbⁿ

and when we do L=L1.l2 at that time don't have knowledge about n ...but here in above language we are concatenating from same language ....so why n is not similar ??

---

$\begin{align*} & L.L = {\color{red}{\left ( a^n.b^n \right )}}.{\color{blue}{\left ( a^k.b^k \right )}} \\ &L.L = {\color{red}{\left ( ab,aabb,aaabbb...... \right )}}.{\color{blue}{\left ( ab,aabb,aaabbb...... \right )}} \\ &L.L = \left \{ {\color{red}{ab}}{\color{blue}{ab}},{\color{red}{ab}}{\color{blue}{aabb}},{\color{red}{ab}}{\color{blue}{aaabbb}},{\color{red}{aabb}}{\color{blue}{ab}} ....\text{etc..} \right \} \end{align*}$

Here whatever dummy n or k you put here , after performing concatanation like above we will end up in the following langage :

$\begin{align*} &L_2 = a^mb^m.a^nb^n \\ \end{align*}$

---

got it thanks !

---

answer should b b).

correct me if wrong.

---

 shefali1

....yes, your approach is fine but here in option b it is say in that "not necessarily regular"...

and L1=L-(a+b)* is leading empty string which is regular....if option b were like this:

1. Both L1 and L2 are context free . then it is also consider as correct option:

---

ok...got it

---

@Praveen Saini

Sir

Plz tell me

For $L_{1},$ if we take $L=a^{n}b^{n}$

And $L_{1}=a^{n}b^{n}-\Phi =a^{n}b^{n}\cap \left ( a+ \right )*=a^{n}b^{n}$

Isnot it  be CFL as maximum? 

Though u have told it Regular, but in the above example regular also not possible. Isnot it? Plz tell me if anything is wrong.

---

Regarding $L_1$, I could just as easily set $y$ to epsilon and we would have $xx$, which is a CSL. But I guess that the reason it's regular is that by setting $x$ to epsilon, it degenerates to $\sum^*$, meaning it can generate not only $xx$ but all possible strings in $\sum^*$.

In the end it all boils down to writing the language as a set...

---

L1 = CFL - Regular => CFL ∩ Compliment(Regular) = CFL ∩ R = CFL

L2 = CFL.CFL = CFL

 

I think, correct option should be B.

Answer 2

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

L₂ = CFL . CFL = CFL

Since CFL Is  Closed Under Concatination.

C Is Answer.

Comments

L1 is regular as per answer key. Correct answer marked in Green.

---

it may b case that cfl also in input x,y... then cfl always subset of regular because it is sigma* .. so ans always phi.

---

**regular is proper subset of cfl

---

@Anirudh 

Suppose L=aⁿbⁿ

L2=L.L = aⁿb^{n .} aⁿbⁿ  

So after concatination it will be CFL ...can u tell me what changes has been happen over here ..