The Gateway to Computer Science Excellence
+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.
in Theory of Computation by Boss (30.2k points)
recategorized by | 349 views

2 Answers

0 votes
Best answer
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 by
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.
by (337 points)

Related questions

Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,645 questions
56,601 answers
195,849 comments
102,206 users