# Is the language L = {(a,b)* | #a * #b is an odd number} regular?

Is the following language regular? $$\{ w \in \{a, b\}^* |\ \text{the product of the number of a's and the number of b's is an odd number}\}$$

If i'm not mistaken the condition is the same as having an odd number of $$a$$'s and an odd number of $$b$$'s. I have tried using the Pumping Lemma without success. So I'm suspecting it's regular. But I can't think of a regular expression or an automaton that accepts it.

It is.

Since only the product of two odd numbers is an odd number, you can construct a DFA that only accepts when #$$a$$ and #$$b$$ are (both) odd.

The followings states would be:

• $$Q_1$$ : #$$a$$ even, #$$b$$ even

• $$Q_2$$ : #$$a$$ even, #$$b$$ odd

• $$Q_3$$ : #$$a$$ odd, #$$b$$ even

• $$Q_4$$ : #$$a$$ odd, #$$b$$ odd (an accepting state)

The transitions are fairly simply, and I'll leave them to you.

To find the equivalent regular expression, try this approach.

If $$\#a$$ and $$\#b$$ are both odd then the total length of the string is even. Divide the string into two character blocks. Each block is either $$aa$$, $$bb$$, $$ab$$ or $$ba$$.

$$aa$$ and $$bb$$ have no effect of the parity of $$\#a$$ and $$\#b$$ so they are equivalent as far as our regular expression is concerned. Similarly $$ab$$ and $$ba$$ both change the parity of $$\#a$$ and the parity of $$\#b$$ so they are also equivalent.

So our regular expression will consist of blocks like $$(aa+bb)$$ and $$(ab+ba)$$.

We don't care how many $$(aa+bb)$$ blocks we see, but we need to see at least one $$(ab+ba)$$ block, so our regular expression will start with

$$(aa+bb)^*(ab+ba) \dots$$

After this we need to see an even number of $$(ab+ba)$$ blocks (remember zero is an even number), possibly interspersed with zero or more $$(aa+bb)$$ blocks. I'll let you take it from there.