3
$\begingroup$

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?

$\endgroup$
3
  • 2
    $\begingroup$ 1 + 10 + 100 is odd. $\endgroup$
    – JeffE
    Feb 4, 2013 at 19:40
  • $\begingroup$ If the sum contains an odd number of odd numbers it will be odd. $\endgroup$ Feb 5, 2013 at 0:19
  • $\begingroup$ 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. $\endgroup$
    – Raphael
    Feb 5, 2013 at 10:20

3 Answers 3

7
$\begingroup$

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

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

$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 $

$\endgroup$
1
  • 2
    $\begingroup$ Great minds think alike ;-) $\endgroup$
    – vonbrand
    Feb 4, 2013 at 18:51
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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