1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.