regular language?

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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 ;-)