Question

Testing whether a language is regular or not. {XwwRY / X,Y∈ (0,1)*, w∈(0,1)+}

Comments

what about w.X.wR.Y , w,X,Y $\epsilon$ (a+b)^+

Answer 1

regular .. look at it this way: we have, x wwr y . x and y can expand from both ends.. only thing required is 00 or 11 in the middle.. which is nothing but the smallest string in wwr. So the language ultimately comes down to, "language containing 00 or 11 as substring"

Answer 2

This language is regular since we have flexibility in choosing x and y we can convert it to set of strings containing 00 or 11 as substring.

suppose x=110001, y=100011, w=0110, w^r=0110, w=011, w^r=110

then XWW^rY = 11000101100110100011 or 1100010111100100011.

so REGULAR EXPRESSION is = (1+0)*(00)(1+0)* + (1+0)*(11)(1+0)*

Answer 3

regular language bcz X and Y are expanded to both sides