GATE2007-31

Question

Which of the following languages is regular?

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

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

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

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

Answer 1

• A. CFL
• B. CFL
• C. 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$
• D. CFL

http://gatecse.in/wiki/Identify_the_class_of_the_language

Comments

But bbaab starting and ending at b is not of form wxw^r....can you please explain

---

@dhingrak   bbaab is in wxw^r where w= b , x= baa w^r = b

---

@Vikrant Singh

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

let W =100, W^R=001 ...

WW^R=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 WW^R 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^R  ..right..?  I mean other strings can also be a part of this language...

why are we not checking W and W^R  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.

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.

---

@Manoj Goswami

Thanks for the reply..

 L1= 100 001  {as WW^R}

L2= 100 110 001 {as WXW^R}

here both L1 and L2 will be accepted by DFA for WXW^R even though accepting  WW^R is not intended ..

so the minimal DFA for WXW^R  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.