Regular Languages

Question

Is this language regular? If yes, how?

L = {wxwR | x, w ϵ {0, 1}*}

wR is reverse of string w.

Thank you!

Comments

yes it is regular.

---

Yes, simple example is,

0(0+1)*0 + 1(0+1)*1  because both variables comes under language (0,1)* we can reorder them and arrange them under X. and the first and last element will be same.

In other case, If X belongs to  (0,1) and W to (0,1)* then it is DCFL = DPDA

W (0+1) Wr  

 

---

No, it's not regular.

For regualar, x should belong to  x  ϵ {0, 1}+ Not  x  ϵ {0, 1}*

 

---

yes, for this case also it will be regular

---

Above given language is complete language over 0,1.

Here is the logic. Keep w =$\epsilon$ =wr and use x to generate any string.

Hence above language is Regular.

Answer 1

the above language is equivalent to " strings starting and ending with same symbol"

-------------------------------------------------------------------------------------------------------------------------------------

let w = 110 and x = 1

then wr = 011.

so string becomes 110 1 011.

we can rewrite this string as

1 10101 1

=> w = 1 and wr = 1  and x = 10101

and regular expression is 1(0+1)*1 + 0(0+1)*0.

we can create a FA for it => language is regular.

Comments

because x can be epsilon also.

SO, it will behave like. $WW{^R}$

---

you gave me string 101101

so i will rewrite the string as w =1 x= 0110 and wr = 1 and then i will check it.

---

Bro, here we can rearrange the center elements. so the constraint will becomes like first and last element should be same. No matter whatever inside may or may not epsilon but still it satisfies our language.

Answer 2

The language is regular , since x is (0 + 1)* you have given the power to x to generate all string now w = (0 + 1)* means w can be epsilon also this means epsilon can also be generated by putting w = epsilon in the wxwr we get x which is (0 + 1)*  that means given language generates all the strings so its regular