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?



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)$


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.