Search code examples
automationcompiler-constructionautomata

Can any tell me the regular expression for the given language?


all strings which contains even number of 0s or even number of 1s. Here I am asking about 'or' not 'and'.

I have come up with this: (1*01*0)*|(0*10*1)* so far...but this seems wrong to me cause when you draw DFA for the above language you can even accept 111 or 000 too.


Solution

  • For zeros, allow for any number of pars of zeros with any number of leading non-zeros and separating non-zeros. And then allow for any trailing non-zeros. If the string does not match this pattern, it has an odd number of zeros.

    (1*01*0)*1*
    

    And to do it for zeros or ones, just copy with 1s instead and add it as an alternative to the whole thing.

    (1*01*0)*1*|(0*10*1)*0*
    

    Also, 111 and 000 both correctly satisfy the condition, because 111 has an even number of 0s and 000 has an even number of 1s. Examples that shouldn't work would be 1101 or 011100.