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.
