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$
  • $\begingroup$ Good luck. (Are you even sure that the language is regular?) $\endgroup$ – Dave Clarke Jul 10 '12 at 15:30
  • $\begingroup$ @DaveClarke I'm going to feel pretty silly if this language isn't regular :P $\endgroup$ – Patrick87 Jul 10 '12 at 15:35
  • $\begingroup$ @Patrick87: And vice versa if it is. $\endgroup$ – Dave Clarke Jul 10 '12 at 16:08
  • $\begingroup$ @Patrick87: Starting to feel silly already. $\endgroup$ – Dave Clarke Jul 10 '12 at 16:09
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$
  • 4
    $\begingroup$ This solution can be simplified to $(aaa)^*(\varepsilon + aab + abb)(bbb)^*$. $\endgroup$ – svick Jul 13 '12 at 9:14

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.