Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
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
up vote 7 down vote accepted

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

share|cite|improve this answer
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 $

share|cite|improve this answer
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.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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