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.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.