'How L={ww^Rx| where w, x belongs to {a,b}^* } is a regular language?
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!
Solution 1:[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?
Sources
This article follows the attribution requirements of Stack Overflow and is licensed under CC BY-SA 3.0.
Source: Stack Overflow
| Solution | Source |
|---|---|
| Solution 1 | Patrick87 |