# Prove that given 2 regular expressions represent the same language

Is it possible to use regular expression identities to prove or disprove that the RE1=0*(0+1)*0* and RE2=(0+1)* represent the same language?

## 1 Answer

Yes:

Clearly, $$L(RE_2)=\Sigma^*$$ ($$\Sigma=\{0,1\}$$ in this case), and obviously $$L(RE_1)\subseteq \Sigma^*=L(RE_2)$$ (since $$RE_1$$ contains only letters from $$\Sigma$$)

Now, we also have $$L(RE_2)\subseteq L(RE_1)$$, since concatenating with a language that contains $$\epsilon$$ is guaranteed to only expand the language. That is, for any $$L$$, and and $$L'$$ such that $$\epsilon \in L'$$, its clear why $$L\subseteq LL'$$. In this case, $$L=L((0+1)^*)$$ and $$L'=L(0^*)$$. Apply this twice from both sides and you will get that $$L(RE_2)\subseteq L(RE_1)$$.

Therefore $$L(RE_1)\subseteq L(RE_2)\subseteq L(RE_1)$$ and thus $$L(RE_1)=L(RE_2)$$