6
$\begingroup$

The language is: $$ L = \{ (a^n) (b^m) \mid n + m = 3k, k \ge 0 \} $$

My attempt at an answer: $$ (a \cup b)^{3k} $$

This will work if the a OR b can change for each instance in the string that is (3k) long. If not, what can I do to fix this?

$\endgroup$
4
  • $\begingroup$ Good luck. (Are you even sure that the language is regular?) $\endgroup$ Commented Jul 10, 2012 at 15:30
  • $\begingroup$ @DaveClarke I'm going to feel pretty silly if this language isn't regular :P $\endgroup$
    – Patrick87
    Commented Jul 10, 2012 at 15:35
  • $\begingroup$ @Patrick87: And vice versa if it is. $\endgroup$ Commented Jul 10, 2012 at 16:08
  • $\begingroup$ @Patrick87: Starting to feel silly already. $\endgroup$ Commented Jul 10, 2012 at 16:09

1 Answer 1

12
$\begingroup$

First off, putting $k$ in the regular expression is not allowed by typical regular expression syntax, unless I'm mistaken. Even adding constant powers is a shorthand notation, not a part of the regular expression formalism. Even if it were possible, using that notation, you could mix $a$s with $b$s, so that not all $a$'s would necessarily come before all $b$s ... so that's not the right direction.

You want strings that begin with $a$s, end with $b$s, and have a total length that is divisible by three. There are a few ways you could go about this. Since you want a regular expression, we might try to develop one directly, without going through a finite automaton.

For a string $x$ from $a^*b^*$ to be in your language, its length must be divisible by three. In other words, it must be true that $|x| = 3k$. Let $x = yz$, where $y \in a^*$ and $z \in b^*$. Then $|x| = |y| + |z|$. So we must have that $|y| + |z| = 3k$. There are only a finite number of ways in which this can happen:

  1. $|y| = 3k_1$ and $|z| = 3k_2$, or
  2. $|y| = 3k_1 + 1$ and $|z| = 3k_2 + 2$, or
  3. $|y| = 3k_1 + 2$ and $|z| = 3k_2 + 1$.

Suppose you can create regular expressions $r_1, r_2, r_3$ corresponding to those three cases. Then you can find the regular expression for your language by taking the union. Let's see how that would work for each case.

  1. This case is easy: the number of $a$'s is divisible by 3, and so is the number of $b$'s. We get a regular expression $r_1 = (aaa)^*(bbb)^*$.
  2. Based on the previous answer, this isn't so bad, either: $r_2 = (aaa)^*a(bbb)^*bb$.
  3. Finally, $r_3 = (aaa)^*aa(bbb)^*b$.

We get an easy regular expression by taking the union of these (I use $+$, but $\cup$ is sometimes also used): $r = r_1 + r_2 + r_3 = (aaa)^*(bbb)^* + (aaa)^*a(bbb)^*bb + (aaa)^*aa(bbb)^*b$.

$\endgroup$
1
  • 4
    $\begingroup$ This solution can be simplified to $(aaa)^*(\varepsilon + aab + abb)(bbb)^*$. $\endgroup$
    – svick
    Commented Jul 13, 2012 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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