Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Will L={xww^R| w, x belongs to {0,1}^+ } is a regular language or not

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

like image 944
SOURAV KABIRAJ Avatar asked Sep 19 '25 16:09

SOURAV KABIRAJ


1 Answers

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.

like image 81
Himanshu Joshi Avatar answered Sep 22 '25 04:09

Himanshu Joshi