Finding a regular expression of a language

Question

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.

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

Evil · Accepted Answer · 2019-05-25 16:46:08Z

2

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

answered May 25, 2019 at 15:21

Evil

9,42511 gold badges31 silver badges52 bronze badges

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$
– Asher Castro
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$
– Asher Castro
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$
– Asher Castro
May 25, 2019 at 16:27

| Show 1 more comment

1 Answer 1