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

-