104 views

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?

1. $L_1|$ is regular but $L_2|$ is not.
2. $L_2|$ is regular but $L_1|$ is not.
3. Both $L_1|$ and $L_2|$ are regular.
4. Both $L_1|$ and $L_2|$ are not regular.
edited | 104 views
0
0
Why do you think that? A proper reasoning would be great.
0
0
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
0
Both are Regular but the reasoning is incorrect. Quotient operation is somewhat different operation. Looks like similar but Isn't at all.

+1 vote

Both L1 and L2 are Regular.

L1 is nothing but the Language formed by taking the Starting 2/3rd 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/3rd 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/kth 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.

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

1