Proving that these two regular languages are equal

139 Views Asked by At

Consider the regular expressions $r_1 = (1+01)^* (0 + \epsilon)$ and $r_2 = (1^* 011^*)^*(0+\epsilon) + 1^* (0+\epsilon)$. I want to show that these the regular expressions generate the same language, i.e., $L(r_1) = L(r_2)$.

I know that I can write $L(r_1) = \{1, 01\}^*\circ\{ 0, \epsilon\}$ and $L(r_2) = ((\{ 1\}^* \circ \{01 \}\circ \{ 1\}^*)^* \circ \{ 0, \epsilon\}) \cup (\{ 1\}^* \{ 0, \epsilon\})$, where $\circ$ means concatenation. I also know that I have to show the double inclusion $L(r_1) \subset L(r_2)$ and $L(r_1) \supset L(r_2)$, but I'm quite stuck at how to do so.