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$.
If you want to turn it into a completely formal proof, you'll need to satisfy a list of axioms and derivation rules, but the proof will likely follow similar steps.