The Gateway to Computer Science Excellence

0 votes

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

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 wxw^{r}.

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

wxw^{r} = 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 x_{new} is 1011x_{old}1101. (x_{old},x_{new}∈ (0,1)^{+ })

w_{new},w_{new}^{r} becomes 0 and 0.

So I can write like w_{new}x_{new}w_{new}^{r}. (w_{new},w_{new}^{r}∈ (0,1)^{+}).

Now see that this is also in form of wxw^{r}. 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.

52,215 questions

59,993 answers

201,197 comments

94,663 users