3

I have already seen that wxw^r is regular as explained in this post Why L={wxw^R| w, x belongs to {a,b}^+ } is a regular language

if i apply the same logic here that w will eat up everything except the last two symbols which can be either 0 or 1

ex : w=101

 x=1010

 w^r=101

 then string is 1010101101

now x will be 10101011
so we can construct a regular expression (0+1)*(0+1)(0+1)

so it should be regular
is my explanation correct or the language will not be regular because where 

i seen the question it was written that the language is not regular with no explanation

Community
  • 1
  • 1
SOURAV KABIRAJ
  • 81
  • 1
  • 1
  • 5

1 Answers1

4

Consider {W X W^r | W,X belongs to (0,1)^+}

Then suppose

W= 101
W^r = 101
X=11

then the String will be

101 11 101
W   X  W^r

then if x consumes all others except the last and first character, then string will look like

  1  011110  1
  W    X     W^r

then also the String follows the pattern W X W^r, note that.

But in your example X W W^r suppose x=11 w=101 w^r=101 then the string will be

11 101 101
X   W   W^r

if now X consume all the character except the last two chars, then string will look like

111011  0  1
   X    W  W^r

note that W & W^r aren't the same, or in some cases, they may be the same, but according to language X W W^r, the last two symbols or last two strings of equal length should be reversal, but they aren't, so the language is not regular.

hoijui
  • 3,615
  • 2
  • 33
  • 41