0 votes 0 votes Check the Language is Regular or Not? WXWR (W,X ∈ (0,1)+) Please Explain. Theory of Computation regular-language + – CHIRAG CHAWLA asked Aug 31, 2018 edited Aug 31, 2018 by MiNiPanda CHIRAG CHAWLA 338 views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Arjun commented Aug 31, 2018 reply Follow Share https://gatecse.in/identify-the-class-of-a-given-language/ 1 votes 1 votes CHIRAG CHAWLA commented Aug 31, 2018 i edited by CHIRAG CHAWLA Aug 31, 2018 reply Follow Share 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 votes 0 votes Shaik Masthan commented Aug 31, 2018 reply Follow Share @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 votes 0 votes MiNiPanda commented Aug 31, 2018 reply Follow Share 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 votes 1 votes Please log in or register to add a comment.
0 votes 0 votes the regular expression is 0(0+1)*0 + 1(0+1)*1 Kalpataru Bose answered Sep 5, 2018 Kalpataru Bose comment Share Follow See all 0 reply Please log in or register to add a comment.