regular language? I need help proving whether this language is regular or not.
$$L = \big\{ w \mid w \in \{a,b\}^*, n_a(w)\text{ is even}, n_b(w)\text{ is even}\big\}$$
That is, the number of $a$'s is even and the number of $b$'s in $w$ is even.
I'm not sure whether I can draw a dfa for this. Thanks, all help is appreciated.
 A: There will be 4 states. One where $n_a(w)$ even and $n_b(w)$ even, one where $n_a(w)$ even and $n_b(w)$ odd, one where $n_a(w)$ odd and $n_b(w)$ even, and one where $n_a(w)$ odd and $n_b(w)$ even.
A: HINT: Try making a DFA with four states, $s_{00},s_{01},s_{10}$, and $s_{11}$. Design it so that when it has read a word with $m$ $a$’s and $n$ $b$’s, it’s in state $s_{m\bmod 2,n\bmod 2}$. (Here $n\bmod 2$ is the remainder when $n$ is divided by $2$, so it’s $0$ if $n$ is even and $1$ if $n$ is odd.)
Added: Here’s your DFA, from the comments, with $q_0$ starred as initial state and underlined as acceptor state. As you can see, each $a$ input moves the automaton horizontally, and each $b$ input moves it vertically, so the states in the top row correspond to an even number of $b$’s, and the states in the lefthand column to an even number of $a$’s.
$$\begin{array}{rcl}
\underline{q_0^*}&\overset{a}\longleftrightarrow&q_1\\
b\updownarrow&&\updownarrow b\\
q_2&\underset{a}\longleftrightarrow&q_3
\end{array}$$
A: Providing a regular expression would work as well. The key point is to observe, that you could split any word of $L$ into chunks $ba^k$ and some simple leftovers.
The only thing we need to fix is that the number of $b$s and $a$s has to be even, but then $ba^*ba^*$ would do the job. One could derive from this a single expression, however, it is much easier to split it in two and intersect (regular languages are closed for intersection).
\begin{align}
L_a &= b^*(ab^*ab^*)^*, \text{ the language of even $a$s}\\
L_b &= a^*(ba^*ba^*)^*, \text{ the language of even $b$s}\\
L &= L_a \cap L_b.
\end{align}
I hope it helps ;-)
