Our alphabet is {a,b} and we need to find a regular expression for the language of all words of the form $a^*b^*$, whose length is a multiple of 3.

Obviously $(aaa)^*(bbb)^*$ is one of the options, but I just can't formalize more options.

Any help will be appreciated.

  • $\begingroup$ "aabbbb" for example. The length is 6 (divisible by 3) but this is not of the form $(aaa)^*(bbb)^*$ $\endgroup$ May 25, 2019 at 13:21
  • $\begingroup$ "bbbaaa" is just another obvious form like I noted above. But what about other forms? How can I formalize them? $\endgroup$ May 25, 2019 at 14:12

1 Answer 1


You have to put your triplets, and use Kleene star: $$(aaa)^*(bbb)^*$$

Now, add cases where number of $a$ is not divisible by 3, say aabbbb, as alternative. $$ (aaa)^*(bbb)^* + (aaa)^*aab(bbb)^* + (aaa)^*abb(bbb)^*$$

  • 1
    $\begingroup$ these are not of the form $a^*b^*$. $\endgroup$
    – Ran G.
    May 25, 2019 at 15:25
  • $\begingroup$ So, can I just take out the wrong ones from his answer? Does $((aaa)∪(aab)∪(abb)∪(bbb))^*$ cover all the options? $\endgroup$ May 25, 2019 at 15:48
  • $\begingroup$ @RanG. Thank you. Sorry, I for unknown reason understood the length must be divisible by 3. Asher, no for the same reason you cannot use alternative, my bad. $\endgroup$
    – Evil
    May 25, 2019 at 15:56
  • 1
    $\begingroup$ Yes, I just realized I was wrong too $\endgroup$ May 25, 2019 at 16:02
  • $\begingroup$ So how about: $((aaa)^*+(bbb)^*)^*+((aaa)^*abb(bbb)^*)+((aaa)^*aab(bbb)^*)$ ? Does this cover all the cases, including the case of $(aaa)^*(bbb)^*$ ? $\endgroup$ May 25, 2019 at 16:27

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.