+1 vote
349 views

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 ?

1. $L_{1}$ is regular language and $L_{2}$ is not regular language.
2. $L_{1}$ is not regular language and $L_{2}$ is regular language.
3. Both $L_{1}$ and $L_{2}$ are regular languages.
4. Both $L_{1}$ and $L_{2}$ are not regular languages.

recategorized | 349 views

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|≥|ν|
by Loyal (6.9k points)
selected
(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.
by (337 points)

+1 vote