GATE CSE 2007 | Question: 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\}$

Comments

How option B CFL please explain

---

wxwR  ∣,w∈{0,1}+ ,x∈{0,1}*

@Vikrant Singh 

it is regular ? if yes  how ? 

---

DFA for option C,

Source: Geeksforgeeks

---

This is not the DFA for option C. Min length string accepted in Option C is 3 and your dfa is accepting a,b.

We need to construct the dfa for reg exp 0(0+1)(0+1)*0 + 1(0+1)(0+1)*1 ie string starting and ending with the same symbol

Answer 1

Correct Option: C

• A. CFL
• B. CFL
• C. Regular, language is string starting and ending with the same symbol and having length at least $3$. e.g. $0x0$ or $1x1$
• D. CFL

http://gatecse.in/wiki/Identify_the_class_of_the_language

Comments

Since, length of x is not restricted, therefore, we just make w as first bit and w$^{r}$ as last bit. 

---

Updated link for the link given in answer:

https://gatecse.in/identify-the-class-of-a-given-language/

---

Regular Expression for Option C) $\left\{wxw^R \mid x, w \in \{0, 1\}^+\right\}$  is → $a(a+b)^+a + b(a+b)^+b$

 

Answer 2

The regular expression corresponding to option C is:
0 (0+1)+ 0 + 1 (0+1)+ 1
Any string which begins and ends with same symbol, can be written in form of “wxwR”
For example consider a string: 10010111, in this string “w=1” , “x= 001011” and wr = 1. Hence any string which begins and ends with either “0” or with “1” can be written in form of “wxwR” and L={wxwR | x,w ϵ {0,1}+ } is a regular language.