2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "aabbbb" for example. The length is 6 (divisible by 3) but this is not of the form $(aaa)^*(bbb)^*$ $\endgroup$ – Asher Castro May 25 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$ – Asher Castro May 25 at 14:12
2
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ these are not of the form $a^*b^*$. $\endgroup$ – Ran G. May 25 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$ – Asher Castro May 25 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 at 15:56
  • 1
    $\begingroup$ Yes, I just realized I was wrong too $\endgroup$ – Asher Castro May 25 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$ – Asher Castro May 25 at 16:27

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.