The Gateway to Computer Science Excellence
0 votes

Check the Language is Regular or Not?

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

Please Explain.

in Theory of Computation by (245 points)
edited by | 47 views
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


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


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 Answer

0 votes
the regular expression is 0(0+1)*0 + 1(0+1)*1
by (375 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,666 questions
56,154 answers
93,719 users