The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+14 votes

Which of the following languages is regular?

  1. $\left\{ww^R \mid w \in \{0, 1\}^+\right\}$

  2. $\left\{ww^Rx \mid x,w  \in \{0, 1\}^+\right\}$

  3. $\left\{wxw^R \mid x, w \in \{0, 1\}^+\right\}$

  4. $\left\{xww^R \mid x, w \in \{0, 1\}^+\right\}$

asked in Theory of Computation by Veteran (59.5k points)
retagged by | 2.2k views

1 Answer

+20 votes
Best answer
  1. CFL
  2. CFL
  3. Regular, language is string starting and ending with the same symbol and having length at least $3$. e.g. $0$x$0$ or $1$x$1$
  4. CFL

answered by Boss (13.5k points)
edited by
But bbaab starting and ending at b is not of form wxw^r....can you please explain

@dhingrak   bbaab is in wxwr where w= b , x= baa wr = b


@Vikrant Singh

Can we consider option A same as that of option C here..?...

let W =100, WR=001 ...

WWR=100 001  ======> the resulting string can  always  be taken as string starting and ending with same symbol..

Should we really need to worry bout the WWR order here.. .plz clarify.

No ,

wwR is just a subset of strings starting and ending with same symbol, as 1011 is also starting and ending with 1 but not wwR. as each symbol of w need to check with wR in reverse.

@Praveen Saini

 The same concept can be applied in case of optin C) WXW ..right..?  I mean other strings can also be a part of this language...

why are we not checking W and W here...? 


#abby murall

In wxw^r |w,x=(a+b)^+

You can give any string it will start and end with same symbol.

011111000 or if 10000111011 bcz here u have x=(0,1)+ machine will consider only first and last part and remaining as X. since x=(0,1)+.

But if you want apply same concept in ww^r it will not accept all string belonging to that languge.


001110 this is inside ww^r but 01110 is not the inside ww^r so it will not accept all the string belonging to this so this is ww^r |w=(a+b)+ is not regular.


@Manoj Goswami

Thanks for the reply..

 L1= 100 001  {as WWR}

L2= 100 110 001 {as WXWR}

here both L1 and L2 will be accepted by DFA for WXWR even though accepting  WWis not intended ..

so the minimal DFA for WXW recognizes two language....Is it acceptable (to my knowledge minimal DFAs are unique) ..?

Yes surely minimal dfa will  unique i.e. starting and ending with same symbol in case of wxw^r....

ww^r contains subset of this languge.So we cant say it is regular.

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

38,039 questions
45,533 answers
48,848 users