# Regular expression for $\{a^k b^m c^n \mid k+m+n \text{ is odd} \}$

I have to make a regular expression from the following laguage:

{$a^kb^mc^n :$ where k + m + n is odd}

Is is possible for the sum of three numbers to be odd (other than three consecutive odd numbers)?

I have this so far:

{(abbbccccc) + (abbbbbccc) + (aaabccccc) + (aaabbbbbc) + (aaaaabccc) + (aaaaabbbc)}

but I am realizing that there are way more possibilities to this pattern... How can I formulate a string that encompasses all of this?

• 1 + 10 + 100 is odd. Feb 4, 2013 at 19:40
• If the sum contains an odd number of odd numbers it will be odd. Feb 5, 2013 at 0:19
• Instead of creating one post per homework exercise, maybe digest the hints from former posts first? We are happy to answer questions, but we are not your TAs.
– Raphael
Feb 5, 2013 at 10:20

What you need is that either exactly two of $k$, $m$, $n$ even, or all three odd, because two odds and an even make an even; and three evens make an even.

An odd number of $a$'s translates to the regular expression $a (a a)^*$, an even number to $(a a)^*$.

Pulling the above together: $$a (a a)^* (b b)^* (c c)^* \mid (a a)^* b (b b)^* (c c)^* \mid (a a )^* (b b)^* c (c c)^* \mid a (a a)^* b (b b)^* c (c c)^*$$

• How does this answer help jsan solve future homework? Teach them how to fish...
– Raphael
Feb 5, 2013 at 10:22
• @Raphael, feel free to edit my answer adding explanation you think is worthwhile. I don't see any. Feb 5, 2013 at 11:50

$a(aa)^\ast (bb)^\ast (cc)^\ast + (aa)^\ast b(bb)^\ast (cc)^\ast + (aa)^\ast (bb)^\ast c(cc)^\ast + a(aa)^\ast b(bb)^\ast c(cc)^\ast$

• Great minds think alike ;-) Feb 4, 2013 at 18:51

There are 6 possibilities which is easy to express as a regular expression $\{a(aa)^*b(bb)^*c(cc)^*|a(aa)^*(bb)^*(cc)^*|(aa)^*b(bb)^*(cc)^*|(aa)^*(bb)^*c(cc)^*\}$

which correspond to the cases all three odd, or two even and one odd. No other case is possible.