67 views

Check the Language is Regular or Not?

WXWR (W,X ∈ (0,1)+)

edited | 67 views
0
In the link,The Regular Expression is a(a+b)+a  +  b(a+b)+b

Through this regular Expression it is only checking first and last bits are same or not

But if String=100111011 where w=100 x=111 w^r=011 then it also accepts this but it should reject it because rev(w) not equals to w^r
0

your string = 100111011 = 1 0011101 1 ===> should be in the language, right?

you are thinking to reject it, but there is another possible way to accept it

+1

Take any string of the form wxwr.

Let w be anything other than epsilon as w ∈ (0,1)+ . I take 01011 then wr becomes 11010.

wxwr = 01011 x 11010

I can extend this x in both directions to consume all the symbols leaving only the symbols at the 2 extremes.

01011 x 11010

I can say my new xnew is 1011xold1101.   (xold,xnew∈ (0,1)+ )

wnew,wnewr becomes 0 and 0.

So I can write like wnewxnewwnewr. (wnew,wnewr∈ (0,1)+).

Now see that this is also in form of wxwr. It is not mandatory to choose a particular w and then proceed. Just check whether a string can be represented in this given form or not maintaining the constraints.

Similarly take any other string and same thing can be done for them.

the regular expression is 0(0+1)*0 + 1(0+1)*1