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$
$\endgroup$
4
-
$\begingroup$ What are $r_1$ and $r_2$? $\endgroup$– GribouillisAug 1, 2021 at 9:10
-
$\begingroup$ Any alphabet. Like $r_1$ = a and $r_2$ = b @Gribouillis $\endgroup$– Anshika SinghAug 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$– Hendrik JanAug 1, 2021 at 15:14
-
$\begingroup$ @HendrikJan Ah, thanks! That clears up my confusion! $\endgroup$– Anshika SinghAug 1, 2021 at 16:20
Add a comment
|