in Theory of Computation edited by
336 views
0 votes
0 votes

Check the Language is Regular or Not?

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

Please Explain.

in Theory of Computation edited by
336 views

4 Comments

1
1
edited by
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
0

@CHIRAG CHAWLA

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

0
0

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.

 

 

1
1

1 Answer

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