How L={ww^Rx| where w, x belongs to {a,b}^* } is a regular language?

Question

I have understood that L={wxw^r|w,x belongs to {a,b}^* } is regular because it turns out to be the pattern of starting and ending with same symbol but I am not getting the proper explanation that how to say L={ww^rx|w,x belongs to {a,b}*} is regular language using DFA design. Please help me in understanding this!

Answer 1

This is a trick question. The language L as you have specified is the language of the regular expression (a + b)*, that is, any string of a's and b's. The trick is that for any string y = s1.s2.s3...sk where si in {a, b}, we can write y = wxw^R where w is the empty string and x = y. Basically, the trick is that we can always choose w to be the empty string, and in that case we are left with L = {x | x in {a, b}^*}, clearly regular. Another way of thinking about it is this: can you find any string of a's and b's that is not in L? Is it not in L even if you take w to be the empty string?