The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+2 votes
86 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.
asked in Theory of Computation by Active (1.1k points)
edited by | 86 views
0
I think answer is d
0
Why do you think that? A proper reasoning would be great.
0
What is the answer?
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 Answer

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


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

answered by Boss (17k points)


Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true

37,120 questions
44,702 answers
127,294 comments
43,767 users