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$.
