3 votes 3 votes A. [(00(0+1)* 11] + [11( 0 + 1)* 00] B. [(00+11) (0+1)+] + [( 0 + 1)+ (00+11)]. C. [(00+11) (0+1)*] + [( 0 + 1)* (00+11)] D. (00+11) (0+1)* (00+11). Theory of Computation theory-of-computation regular-expression peter-linz + – im.raj asked Jun 16, 2016 im.raj 20.8k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
Best answer 12 votes 12 votes The correct answer would be C. The regular expression can be categorized into two subparts. $R= L_1 + L_2 $ $L_1$ = The strings which begin with $00$ or $11$. $L_2$ = The strings which end with $00$ or $11$. Let us find out $L_1$ and $L_2$. $L_1$ = $(00 + 11)$ . (any number of 0's and 1's ) $L_1$ = $(00 + 11). {(0+1)}^{*}$ Similarly $L_2$ = (any number of 0's and 1's ) . $( 00 + 11)$ = ${(0+1)}^{*} (00 + 11) $ Hence R= $[(00+11) {(0+1)}^{*}] + [{( 0 + 1)}^{*} (00+11)]$. rude answered Jun 16, 2016 • selected Jun 16, 2016 by im.raj rude comment Share Follow See all 2 Comments See all 2 2 Comments reply Deep99 commented Jun 17, 2016 reply Follow Share why option D is not correct (00+11) (0+1)* (00+11). it is also going to start with either 00 or 11 and ends with either 00 or 11. 1 votes 1 votes Jason GATE commented Jul 20, 2016 reply Follow Share Sir that will not accept strings like 00,11. 0 votes 0 votes Please log in or register to add a comment.
0 votes 0 votes Ans C) [(00+11) (0+1)*] + [( 0 + 1)* (00+11)] here either start with 00 or 11 , then minimum string will be 00 or 11 if end with 00 or 11 the also minimum string is 00 or 11 Here ⋋ also accepted, but that is not mentioned in any option srestha answered Jun 16, 2016 srestha comment Share Follow See all 5 Comments See all 5 5 Comments reply Show 2 previous comments LeenSharma commented Jun 18, 2016 reply Follow Share @Deep99 Option (d) is a regular expression which denotes a Language which accept all the string which begin "and " end with 00 and 11 1 votes 1 votes sunil maddheshiya commented Jul 13, 2016 reply Follow Share Option d is not correct b/c minimum string accepted by regular expression is 00 or 11...that is not fullfill by option d.. 0 votes 0 votes Shubhanshu commented Jul 3, 2017 reply Follow Share Counter case for D) is it does not generate string 0010 which is correct as per given question because it is starting with 00 and it doesn't matter that it should be end with either 00 or 11. But from option C) we can do that. Hope this Helps readers. 0 votes 0 votes Please log in or register to add a comment.