3.1k views

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\}$

retagged | 3.1k views

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

http://gatecse.in/wiki/Identify_the_class_of_the_language

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

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

0

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.

+3
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.
0

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

+1

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

Eg.

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.

0

@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) ..?

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

1
2