Regular expression for language with even number of 0's and 1's

Question Detail: 

Let $\Sigma=\{0,1\}$. What is the regular expression for the language of all strings with an even number of $0$'s and an even number of $1$'s?

If we only require an even number of $0$'s, the language $(1^*)\mid(1^*01^*01^*)^*$ works. But once there is a requirement on both $0$'s and $1$'s, I'm not sure how to do it.

Asked By : mba

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/41932

Answered By : Hendrik Jan

Constructing regular expressions is usually more complicated than programming finite state automata. The standard way would be to construct a FSA and translate that one into a regular expression using standard techniques.

But if you prefer, it can be done directly, in two steps. Start by making two regular expressions $\alpha$ and $\beta$.

• First $\alpha$ specifies strings with even number of $1$'s, and exactly two $0$'s, one of which is the last symbol of the string.
• Similarly $\beta$ specifies strings with odd number of $1$'s, and exactly two $0$'s, one of which is the last symbol of the string.

Then build an expression for strings that have an even number of $0$ ánd an even number of $1$'s based on $\alpha$ and $\beta$.