Prove regular expressions are equal: $0^*1(1 + 00^*1)^*$ is $(0 + 1)^*1$

Question

I tried: $0^*1(1 + 00^*1)^* = 0^*1(1^* (00^*1)^*)^*$

but after that I'm not sure how to get further. I can definitely see that this expression always ends with 1 and that's what $(0 + 1)^*1$ but I don't see a rigorous chain of arguments to prove it.

I also tried constructing a DFA which is definitely useful in seeing the RE more clearly but still... no proof.

Answer 1

I believe the DFA for the former regular expression would be too complicated to comprehend. Instead, as you observed that the latter regular expression gives all strings ending with $1$, we show that the regular expressions are equal by showing:

1. $0^*1(1+00^*1)^*$ can generate any string ending with $1$;

2. All strings generated by $0^*1(1+00^*1)^*$ ends with $1$.

I will show 1. and leave 2. as exercise. Pick any string ending with $1$, and we use the following algorithm to generate this string from $0^*1(1+00^*1)^*$:

1. If there are any leading $0$s, use $0^*$ for them.
2. A $1$ must come after the leading $0$s, and we have a $1$ next in line in the regex.
3. If there are any further $1$s, they either come with some leading $0$s (counting from the last $1$) or is directly after the previous $1$.

• For the first case, we can handle it with $(00^*1)$.
• For the second case, we can handle it with $1$.

For example, the string $00010010011$ can be handled as $0^*1(00^*1)(00^*1)(1)$ which is valid in $0^*1(1+00^*1)^*$. Now it remains to be shown that $0^*1(1+00^*1)^*$ always end in $1$.