[Solved]: Regular expression for $\{a^k b^m c^n \mid k+m+n \text{ is odd} \}$

Problem Detail: 

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?

Asked By : jsan

Answered By : vonbrand

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)^* $$

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/9478