TOC Gatebook

Question

Let L = {xy | xwy  L1, |x| = |w| = |y|}. Then L is(L1 is regular)

(A). Regular

(B). Non regular

(C). May be regular

(D). None

Answer 1

it should be may be regular... as L contains strings in 'xy' form where |x| = |y| and any string in L has length |x|+|y| = 2|x|=2|y| that means length is always even now the language can be either aⁿbⁿ [this has even len] or (aa+bb)* hence language may be regular not always.

Comments

The example is not clear.

---

@arjun sir if i take any one set of strings from regular language L1 and  make it prove as non regular can't i say this is not always regular. ? Like L1 : a*b*c* , then if i consider all sets of strings where b* goes to epsilon then i enumerate over same length of a's and b's ... I can have L = {ab,aabb,aaabbb......} --> aⁿ bⁿ

//Now to prove ab belongs to L1 we can write in xwy form as : ab 

Similarly aabb belongs to L1 as we can write in wxy form as : aabb ... so L1 cannot be said as always regular.

Please correct me if i got wrong somewhere.

---

@arjun sir ..am i still wrong ? i checked it again that's why asking again.

---

Again not getting. If you take $L_1 = a^*b^*c^*$, then $L$ should contain $ab, abc, ac \dots$ as $abbb, abcccc, accc \dots$ are in $L_1$.

Answer 2

It is a tricky question..

See given in the language L1 we have |x| = |w| = |y|

But in language L we do not have the w component .Only x and y components are there..

And we require |x| = |y| as L is defined in terms of L1 in the question..

So as |x| = |y| , thus it is guaranteed that any string belonging to language L is an even length string as then only |x| = |y| is satisfied..

We know we can make a DFA of 2 states for the even length strings with say Q₀ state corresponding to even length strings and Q₁ for odd length strings..

Alternatively , we can have regular expression as : [(a + b)²]*  =  (aa + ab + ba + bb)*..

Thus the language L is regular..

Hence option A) is correct ..

Comments

Very nice question : )

Not able to find any counter example for L not being regular. 

But working on one example, Please check it- 

If L1 = (abbaca)*,

Then what would be regular expression for L ?

Not able to write regular expression for L so please help. 

---

@Vijaycs. We are getting strings like L = [ abca + abba(caab)*baca ]  which is regular, right?

---

^ seems correct to me .. (y)

Thank you : )