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.2k
- Engineering Mathematics 5k
- Digital Logic 2k
- Programming & DS 3.6k
- Algorithms 3.1k
- Theory of Computation 3.9k
- Compiler Design 1.5k
- Databases 2.9k
- CO & Architecture 2.5k
- Computer Networks 2.9k
- Non GATE 1k
- Others 1.4k
- Admissions 412
- Exam Queries 419
- Tier 1 Placement Questions 17
- Job Queries 55
- Projects 9

34,947 questions

41,991 answers

119,239 comments

41,484 users