The Gateway to Computer Science Excellence

First time here? Checkout the FAQ!

x

+2 votes

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?

- $L_1|$ is regular but $L_2|$ is not.
- $L_2|$ is regular but $L_1|$ is not.
- Both $L_1|$ and $L_2|$ are regular.
- Both $L_1|$ and $L_2|$ are not regular.

+1 vote

**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 :

- All categories
- General Aptitude 1.4k
- Engineering Mathematics 5.9k
- Digital Logic 2.3k
- Programming & DS 4.2k
- Algorithms 3.6k
- Theory of Computation 4.6k
- Compiler Design 1.7k
- Databases 3.3k
- CO & Architecture 2.9k
- Computer Networks 3.3k
- Non GATE 1.2k
- Others 1.3k
- Admissions 506
- Exam Queries 480
- Tier 1 Placement Questions 22
- Job Queries 64
- Projects 15

40,734 questions

47,462 answers

145,528 comments

62,224 users