2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.