0 votes 0 votes if this is regular and its Regular expression can be written as [(0+1)*0(0+1)*0]+ [(0+1)*1(0+1)*1] then it will also include those strings where first W2 second W2 are different. I am not getting this somebody please clear this doubt. Prerna Chauhan asked Dec 23, 2016 Prerna Chauhan 966 views answer comment Share Follow See all 11 Comments See all 11 11 Comments reply Show 8 previous comments Arjun commented Dec 24, 2016 reply Follow Share Simple reason - we cannot write a regular expression for it. $L$ does include string of the form starting and ending with same letter and having at least four letters. But it also has strings of the form, $00111001, 000011100001, 0001000001 \dots$ where we need a power to ensure the first part matches exactly like the last part. 0 votes 0 votes Prerna Chauhan commented Dec 24, 2016 reply Follow Share okay so even if we make x and y to eat up the entire middle part leaving last two characters we can have 0 in the beginning and 1 in the end therefore we can't write RE for this? am i getting it right? 0 votes 0 votes Arjun commented Dec 24, 2016 reply Follow Share yes, some strings (infinite of them) cannot be captured by a regular expression. 2 votes 2 votes Please log in or register to add a comment.
Best answer 2 votes 2 votes RE = (0 + 1)+ 0 (0 + 1)+ 0 + (0 + 1)+ 1 (0 + 1)+ 1 here w2 is either 0 or 1. It can be any other string also, but in all such strings this condition also gets satisfied as a string can start with either 0 or 1 only. RAJESHWAR YADAV answered Dec 23, 2016 • selected Dec 24, 2016 by Arjun RAJESHWAR YADAV comment Share Follow See all 4 Comments See all 4 4 Comments reply Arjun commented Dec 24, 2016 reply Follow Share your RE generates 0001, which is not in $L$. 0 votes 0 votes focus _GATE commented Dec 24, 2016 reply Follow Share @arjun sir is there any flaw in my answer .if it is wrong than correct it .plz .thanks . 0 votes 0 votes Arjun commented Dec 24, 2016 reply Follow Share it is not correct. Answer is given in question only. 0 votes 0 votes RAJESHWAR YADAV commented Dec 24, 2016 reply Follow Share answer is corrected 0 votes 0 votes Please log in or register to add a comment.
1 votes 1 votes w1 w2 w3 all are independent but there in one string matching of w2 with itself so it should be done by LBA so its CSL language hence recursive d) option answer . focus _GATE answered Dec 24, 2016 focus _GATE comment Share Follow See all 0 reply Please log in or register to add a comment.