1 votes 1 votes Complement of (0+1)*1 ?? my answer is (0+11*0)* given answer is (1*0)* please give detail explanation! Theory of Computation theory-of-computation finite-automata regular-expression + – learner_geek asked Aug 15, 2017 learner_geek 708 views answer comment Share Follow See all 3 Comments See all 3 3 Comments reply Tesla! commented Aug 15, 2017 reply Follow Share I guess both are correct as one re can have many representation 1 votes 1 votes learner_geek commented Aug 15, 2017 reply Follow Share @tesla please convert (0+11*0)* into (1*0)* how to convert?? as we know 11* is 1+ but how 0+11* is 1* 0 votes 0 votes Tesla! commented Aug 15, 2017 reply Follow Share Conversation is difficult task try to draw minimize dfa of both you should get same dfa 0 votes 0 votes Please log in or register to add a comment.
Best answer 1 votes 1 votes Both the answers are correct! (0+11*0)* = ( ($\varepsilon$ + 11*)0 )* = (1*0)* just_bhavana answered Aug 15, 2017 • edited Aug 15, 2017 by just_bhavana just_bhavana comment Share Follow See all 6 Comments See all 6 6 Comments reply learner_geek commented Aug 15, 2017 reply Follow Share @ just_bhavana it means (0+11*0)* = ( 0(εε + 11*) )* = (0*1*)* is also true 0 votes 0 votes just_bhavana commented Aug 15, 2017 reply Follow Share No, if you expand your expression, you'll get 0 + 011* which is not the correct RE. If you notice, 11* is on the left of 0. So (ε + 11*)0 would be most appropriate. It's like A + AB* = A(ε + B*) = AB* and not B*A 1 votes 1 votes learner_geek commented Aug 15, 2017 reply Follow Share @ just_bhavana thanks i got it 1 votes 1 votes joshi_nitish commented Aug 15, 2017 reply Follow Share @just_bhavna (0+11*0)* = ( (εε + 11*)0 )* = (1*0*)*, this is not correct. xtreme RHS is equivalent to (0+1)*(universal language), which is not equivalent to xtreme LHS 1 votes 1 votes just_bhavana commented Aug 15, 2017 reply Follow Share It was a typo, have a look.. edited it 5 mins ago 0 votes 0 votes learner_geek commented Aug 15, 2017 reply Follow Share @joshi_nitish thanks for your error detection I also missed it 0 votes 0 votes Please log in or register to add a comment.