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.

- All categories
- General Aptitude 1.8k
- Engineering Mathematics 7.4k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.1k
- Non GATE 1.5k
- Others 1.7k
- Admissions 595
- Exam Queries 576
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 17

50,666 questions

56,154 answers

193,757 comments

93,719 users