A regex that matches strings containing an even number of 0’s or even number of 1’s

Question

I need to write a regex that matches strings containing an even number of 0’s or even number of 1’s. (Alphabet Σ= 0,1)

I have already tried (1*(01*01*)*)|(0*(10*10*)*) but this can not recognize some strings like the whole string of 11000. I know that the part (0*(10*10*)*) of my regex matches 11000. But I don't know what's the problem.

Please consider that I can only use *, |, ?, range and excluded range. Thanks in advance.

Answer 1

The set of all binary strings built from the alphabet $\Sigma=\{0,1\}$ can be written as \begin{align*} 1^{*}\left(01^{*}\right)^{*}\tag{1} \end{align*} since each binary string can be grouped into blocks, where each block starts with a $0$ followed by zero or more $1$'s and the word may start with zero or more $1$'s. Symmetrically we can also specify the set of all binary strings as \begin{align*} 0^{*}\left(10^{*}\right)^{*}\tag{2} \end{align*} An even number of $0$s can be assured by doubling each group $01^{*}$ in (1) and symmetrically an even number of $1$s by doubling each group $10^{*}$ in (2). We so derive OPs regexp stated in the problem. \begin{align*} \left(1^{*}\left(01^{*}01^{*}\right)^{*}|0^{*}\left(10^{*}10^{*}\right)^{*}\right)\tag{3} \end{align*}

We extend the regexp in (3) by

• enforcing at least one occurrence of an even number of $1$'s resp. $0$'s and

• we also put zero or more $1$'s at the end of the left-hand alternative of (3) and zero or more $0$'s at the end of the right-hand alternative.

We so obtain \begin{align*} \color{blue}{\left(1^{*}\left(01^{*}01^{*}\right)\left(01^{*}01^{*}\right)^{*}1^{*}\right)|\left(0^{*}\left(10^{*}10^{*}\right)\left(10^{*}10^{*}\right)^{*}0^{*}\right)} \end{align*}

Note: If we additionally allow the '$+$' quantifier, the regexp can be written as \begin{align*} \left(1^{*}\left(01^{*}01^{*}\right)^{+}1^{*}\right)|\left(0^{*}\left(10^{*}10^{*}\right)^{+}0^{*}\right) \end{align*}