Is the following equivalence true?

$$(r_1^*r_2^*)^* = (r_1 + r_2)^*$$

I think these are equivalent since both the expressions generate the same strings: $\{\epsilon,r_1,r_2,\dots\}$ etc.

  • $\begingroup$ What are $r_1$ and $r_2$? $\endgroup$ Aug 1, 2021 at 9:10
  • $\begingroup$ Any alphabet. Like $r_1$ = a and $r_2$ = b @Gribouillis $\endgroup$ Aug 1, 2021 at 10:17
  • 4
    $\begingroup$ Yes, they are equivalent. The expressions denote the same language for every language $r_1$ and $r_2$. This can be shown using finite state automata: Regular expression $(a^{*}b^{*})^{*} = \left( a+b \right)^{*}$ proof Alternatively there is Kleene algebra which has equational rules that characterize regular expression equivalence. $\endgroup$ Aug 1, 2021 at 15:14
  • $\begingroup$ @HendrikJan Ah, thanks! That clears up my confusion! $\endgroup$ Aug 1, 2021 at 16:20


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.