Regular expression for bit strings with even number of 1s

compiler-construction, grammar, regex

Solution

A if false. It doesn't get matched by 0110 (or any zeros-only non-empty string)

B represents OK. I won't bother proving it here since the page margins are too small.

C doesn't get matched by 010101010 (zero in the middle is not matched)

D as you said doesn't get matched by 00 or any other # with no ones.

So only B

Problem

Let `L= { w in (0+1)* | w has even number of 1s}`, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expressions below represents L? A) (0*10*1)* B) 0*(10*10*)* C) 0*(10*1)* 0* D) 0*1(10*1)* 10* According to me option `D` is never correct because it does not represent the bit string with zero 1s. But what about the other options? We are concerned about the number of 1s(even or not) not the number of zeros doesn't matter. Then which is the correct option and why?

Original source