I cannot figure out how to go about proving this statement in regular expression.

$$ L(R_1) \subseteq L(R_2) \subseteq L(R_3) \implies L(R_1^*+R_3)^* \subseteq L(R_2^*+R_3^*) $$

Here's what I have so far:

Since $L_1 \subseteq L_2 \implies L_1^* \subseteq L_2^*$ then $L(R_1) \subseteq L(R_2) \subseteq L(R_3) \implies L(R_1)^* \subseteq L(R_2)^* \subseteq L(R_3)^*$. If $x$ belongs to $L(R_1)$ then $x$ also belongs to $L(R_2)$ and $L(R_3)$ and if $y$ belongs to $L(R_1)^*$ then $y$ also belongs to $L(R_2)^*$ and $L(R_3)^*$. I'm not sure how to go from here to show that $(y+x)^* \subseteq (y+y)$.

  • $\begingroup$ Try showing that both languages on the right-hand side are in fact equal to $L[R_3^*]$. For this, it suffices that $L[R_1],L[R_2] \subseteq L[R_3]$. $\endgroup$ Nov 2 '20 at 21:06

Your Answer

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

Browse other questions tagged or ask your own question.