Redirected
recategorized by
1,585 views
1 votes
1 votes

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 by

3 Answers

Best answer
0 votes
0 votes
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|≥|ν|
selected by
3 votes
3 votes

(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.

edited by
0 votes
0 votes
(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.

Related questions

5 votes
5 votes
1 answer
3