Regular Language

Question

Let $L\mid$ be a regular language and

$L_1| = \{x|\mid\text{there exist y}\mid \text{so that xy} \in L| \text{ and} \mid x \mid = 2 \mid y\mid \mid \}$

$L_2| = \{x|\mid\text{there exist y}\mid \text{so that yx} \in L| \text{ and} \mid x \mid = 2 \mid y\mid \mid \}$

Then which of the following is necessarily correct?

• A. $L_1|$ is regular but $L_2|$ is not.
• B. $L_2|$ is regular but $L_1|$ is not.
• C. Both $L_1|$ and $L_2|$ are regular.
• D. Both $L_1|$ and $L_2|$ are not regular.

Comments

I think answer is d

---

Why do you think that? A proper reasoning would be great.

---

What is the answer?

---

i think both are regular

If L is regular

Right Quotient of L i.e xy belongs to L =L1 is also regular

Left Quotient of L i.e yx belongs to L =L2 is also regular

---

Both are Regular but the reasoning is incorrect. Quotient operation is somewhat different operation. Looks like similar but Isn't at all.

Answer 1

Both L1 and L2 are Regular.

L1 is nothing but the Language formed by taking the Starting 2/3^rd part of all the Strings (Wherever Possible i.e. Those Strings whose Length is Multiple of 3 in L) in L. Similarly, L2 is nothing but the Language formed by taking the Ending 2/3^rd part of all the Strings (Wherever Possible i.e. Those Strings whose Length is Multiple of 3 in L) in L.

And Set of Regular Languages is closed under Such Operations. And By Such Operations I mean "Taking some 1/k^th portion (from starting or from ending)" of  all the strings of the language. 

---

You must be familiar with the standard Half(L) operation on languages : 

HALF(L) = {x ∣ xy ∈ L for some y with |y| = |x| }

And Set of Regular Languages is closed under "HALF" Operation. 

---

Useful Links :

https://cs.stackexchange.com/questions/29767/proving-regularity-of-languages-that-are-1-k-of-an-already-known-regular-languag

https://math.stackexchange.com/questions/1539658/automata-prove-that-if-l-is-regular-than-halfl-is-regular-too

https://cs.stackexchange.com/questions/29924/show-that-the-regular-languages-are-closed-against-taking-the-second-half