Question

Which of the following languages is regular?

Answer 1

L = $\{wx{w}^R\mid x,wϵ(0,1{)}^{+}\}$ is regular, Put w as 0 and 1 which are its minimal string values and get a minimal expression

r = [0(0+1)${}^{+}$0]+[1(0+1)${}^{+}$1]

Now putting w as any other string will not create any new string not generated by r.

Example if we put w as say 01, then $wx{w}^R=01(0+1{)}^{+}10$ which is already generated by the first part of r

Similarly if we put w as say 10, then $wx{w}^R=10(0+1{)}^{+}01$ which is already generated by the second part of r

So, L = L(r)

So the regular expression for L is

r = $\left[0\right(0+1{)}^{+}0]+[1(0+1{)}^{+}1]$

That is, L reduces to the language of words which starts and ends with the same symbol. since we are able to write a regular expression for L therefore L is regular.