Finding a regex/DFSA

Question

Consider the following language over alphabet $\Sigma = \{0, 1\}$:

$\{0^n 1^m : n, m \geq 0 \text{ and } n + m \text{ is odd}\}$

How would you determine the regular expression/DFSA for this language?

Based on my understanding I cant directly use $n,m$ in the expression, so I am at a lost on how to do this

Answer 1

Let $Q = \{\, e_0, e_1, o_0, o_1 \,\}$ be the set of states. Let $e_0$ be the initial state and $\{\, e_1, o_1 \,\}$ the set of accepting states. The transitions are: $$ \begin{align*} \delta(e_0,0) &= o_0 \\ \delta(e_0,1) &= o_1 \\ \delta(o_0,0) &= e_0 \\ \delta(o_0,1) &= e_1 \\ \delta(e_1,1) &= o_1 \\ \delta(o_1,1) &= e_1 \end{align*} $$ No transitions are defined for input letter $0$ from the $e_1$ and $o_1$ states. Alternatively one can add a trap state to get a complete transition function.

This automaton accepts $L = \{\, 0^n1^m : n,m \geq 0 \text{ and $n+m$ is odd}\,\}$.

The idea is very simple: even plus even is even, odd plus odd is even, and the other two cases give an odd sum.

You can also see the problem as one of intersecting two regular languages. One is $0^*1^*$ and the other one is the language of all strings in $\Sigma^*$ of odd length, for instance, $\Sigma(\Sigma\Sigma)^*$, where $\Sigma$ stands for $(0+1)$. Each of these two languages has a two-state acceptor. When those two automata are composed, one gets the four-state automaton above.

We cannot obtain a regular expression for $L$ by simple intersection of two regular expressions above, but we can simply go back to the observation that in a word of the language there's either an odd number of $0$s or an odd number of $1$s. Hence $$ (0(00)^*(11)^*) + ((00)^*1(11)^*) $$ describes $L$. Of course, this expression suggests another way to find an automaton for $L$, namely from the automata that accept $0(00)^*(11)^*$ and $(00)^*1(11)^*$. This other approach is a bit more laborious than the one based on intersection.

Answer 2

The states $s_1$ and $s_2$ below represent states with odd and even number of $0$'s and $s_3$, $s_4$ represent odd and even number of $1$'s. The basic idea is that when there are odd (even) number of $0$'s then the number of $1$'s should be even (odd).

Or as noted by Henning Makholm, one can do away with $s_2$ to get a five state machine as below:

Can you form regex using the same idea? Only those strings which have odd number of zeros followed by even number of ones or even number of zeros followed by odd number of ones are to be represented.