UGC NET CSE | August 2016 | Part 3 | Question: 55

Question

Given the following two languages :

$L_{1} = {uww^{R} ν | u, v, w \in (a, b)^{+}}$

$L_{2} = {uww^{R} ν | u, ν, w \in (a, b)^{+} , |u| \geq |ν|}$

Which of the following is correct ?

• A. $L_{1}$ is regular language and $L_{2}$ is not regular language.
• B. $L_{1}$ is not regular language and $L_{2}$ is regular language.
• C. Both $L_{1}$ and $L_{2}$ are regular languages.
• D. Both $L_{1}$ and $L_{2}$ are not regular languages.

Comments

option 1??

---

Plz explain..

Answer 1

Option A is correct

L1 is regular B/C      u and  v can eat up all string except 2 length string one is w and wr

now the language became string contating aa or bb

L2 is not regular B/C we need stack to compare length of

|u|≥|ν|

Answer 2

(A) is the correct option! $L_1$ is regular while $L_2$ is non-regular.

For $L_1$ since $ww_R$ is there, at some point of the string we should have either $aa$ or $bb$.

Regular expression for L1:  $r1= (a+b)^{+}(aa +bb)(a+b)^{+}$

while in Language $L_2$ there is a comparison between the length of u and v which can't be done by DFA.

Comments

How can L1 be regular?
Someone please explain,

aaaabbaabbabababa

u=aaa

w=abba

Please Parse for this string if someone understood the example above.

---

@Barney Ross  in your given string we can take w is a then wr will be a also which your string contain and before first a we can consider the whole string as u and after the second a we can take the whole remaining string as v bcoz we can see that in question the size of u and v are not fixed (which is fixed ie has comparison in L2). so in simple language we can say that if any string contain aa or bb then it will comes under L1 hence it is regular , you can compre this question to a standard question WXWr  i hope u know this is also regular by similar method.

---

worst explanation.

Answer 3

(A) is the correct option! L1 is regular while L2 is non-regular.

For L1 since ww^r is there, at some point of the string we should have either aa or bb.

while in Language L2 there is a comparison between the length of u and v which can't be done by DFA.