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

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.

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

• Hi just wondering if you could check my answer. my dfa is the following: a b q0 q1 q2 q1 q0 q3 q2 q3 q0 q3 q2 q1 – Thresh Feb 12 '13 at 6:15
• @TonsOfDamage: I’m interpreting that to mean that there are $a$-transitions from $q_0$ to $q_1$, $q_1$ to $q_0$, $q_2$ to $q_3$, and $q_3$ to $q_2$, and $b$-transitions from $q_0$ to $q_2$, $q_1$ to $q_3$, $q_2$ to $q_0$, and $q_3$ to $q_1$. If $q_0$ is both your initial state and your only acceptor state, that DFA works fine. – Brian M. Scott Feb 12 '13 at 6:27
• Yes, you interpreted that right. However, I made my initial state q0 and my final/acceptor state q1. Could you tell me if this works? or if q0 should be my initial and accepting state? – Thresh Feb 12 '13 at 6:42
• @TonsOfDamage: $q_0$ should also be your acceptor state. If you start in $q_0$, after an even number of $a$’s you’ll be in $q_0$ or $q_2$, and after an even number of $b$’s you’ll be in $q_0$ or $q_1$; you want both, so you want to be in $q_0$. If you’re in $q_1$, you’ve read an odd number of $a$’s and an even number of $b$’s. – Brian M. Scott Feb 12 '13 at 6:49
• Alright, I understand now. Thank you very much for your help. – Thresh Feb 12 '13 at 6:50

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