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. Commented Feb 4, 2013 at 19:40
• If the sum contains an odd number of odd numbers it will be odd. Commented 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. Commented 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... Commented Feb 5, 2013 at 10:22
• @Raphael, feel free to edit my answer adding explanation you think is worthwhile. I don't see any. Commented 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 ;-) Commented 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.