#TOC Regular Language Is this a regular set?

Question

WXW^R where W,X belongs to (0,1)*

W^R is reverse of a string!

Comments

Yes this is a regualar set , $\sum^{*}$

---

Can you please explain it in a bit detail?

---

L = $w\,x\,w^r$

let we put w = $\varepsilon$ , so $L^{'}=x$ and since x $\epsilon$ $(0,1)^*$

so $L^{'}=(0,1)^*=\sum^*$

$L=L^{'} \bigcup \left \{ ... \right \}=\sum^*\bigcup \left \{ ... \right \}=\sum^*$

So, L is regular

---

Thanks mate

Answer 1

I don't think this is a regular set,as no Finite automaton can be constructed to check whether the string after "x" is reverse of w or not.PDA can be constructed.This can also be proved by Pumping Lemma as follows:

$Step\ 1:Player\ 1\ chooses\ any\ arbitary\ n.\\Step\ 2:Player\ 2\ chooses\ a\ string\ w=0^{n-k}1^{k}x0^{k}1^{n-k}.\\Step\ 3:Player\ 1\ chooses\ 0^{n-k}\ as\ a\ and\ 1^{k}\ as\ y\ and\ rest\ a\ c\ as\ \left | ab \right |\leq n.\\Step\ 4:Player\ 2\ sets\ i=2\ such\ that ab^{2}c=0^{n-k}1^{2k}x1^{k}0^{n-k}\ which\ \notin\left \{L:L=WxW^{R} \right \}$

Hence,$WxW^{R}$ is not a regular language.Please feel free to correct me if I'm wrong :)

Comments

It is regular .

Answer 2

Yes it is regular.