# Equivalent regular expressions - Proof

I came across the following two regular expressions $$r_1 = 0^+(10^+0)^∗0^*$$ and $$r_2 = 0^+(10^+0)^∗$$.

I know, in general, proving if two regular expressions are equivalent is hard in terms of time complexity, and that there are several algorithms to determine this. (e.g, convert regex to DFAs.) However, I wanted to know if there is a simpler method for this particular example.

Firstly, they seem to be equivalent.

Intuitively, $$r_1$$ describes all the words that $$r_2$$ does since both expressions are the same except for the $$0^*$$ at the end of $$r_1$$.

Next, let us rearrange $$r_1$$ and $$r_2$$ like so:

$$r_1 = 0^+(100^+)^∗0^*$$

$$r_2 = 0^+(100^+)^∗$$

Note that although we changed the order of the expression in the parentheses, it still expresses the same idea, which is zero or more repetitions of one 1 followed by at least two zeroes.

This english description seems to apply even when we append the $$0^*$$ at the end of $$r_1$$. Because if we had $$m$$ zeroes at the end of a word (e.g, 00000100100000), all we would have to do is to use $$m$$ zeroes for the last repetition of the expression in the parentheses, and just ignore the $$0^*$$.

This is kind of like my intuition, but I wanted to know if there is any formal proof for this? Or even, I might be wrong, and these regex are not equivalent and there is a counterexample.

Using $$s^* = \epsilon + s^*s$$, we have $$0^+(10^+0)^*0^* = \\ 0^+ (\epsilon + (10^+0)^*10^+0)0^* = \\ 0^+0^* + 0^+(10^+0)^*10^+00^*$$ Similarly, $$0^+(10^+0)^* = 0^+ (\epsilon + (10^+0)^*10^+0) = \\ 0^+ + 0^+(10^+0)10^+0$$ Therefore it suffices to convince oneself that $$0^+0^* = 0^+$$ and $$0^+00^* = 0^+0$$.