# Simplifying regex expression (L+M*)*

To simplify it, it seems that we can do $$(L+M^*)^* = (L+M)^*$$, but I also need to prove it.$$(L+M)^* ⊆ (L+M^*)^*$$ seems straight forward. However, $$(L+M^*)^* ⊆ (L+M)^*$$ is what I couldn't figure out. Should I use $$(L^*M^*)^*$$ instead of $$( L+M)^*$$? If I use it and do induction on k, $$u ∈ (L+M^*)^*$$ and u = (v1+m1)...(vk+mk); j = 1...k, vj ∈ L, and mj ∈ M*.

For k=1, $$v1⊆L ⊆ (L^*M^*)^*$$ and $$m1⊆M^* ⊆ (L^*M^*)^*$$, $$v1+m1⊆ (L^*M^*)^*$$. How do I continue afterwards?

• Try induction on the length of the string $x$. Let $L_1 = (L+M^\ast)^\ast$ and $L_2 = (L+M)^\ast$. Observe for $|x|=0 \implies x=\epsilon$ which belongs to both languages. Now assume for $x\in \{0,1\}^{k}, k\leq n$, $x\in L_1 \implies x\in L_2$. Now take a string $x\in L_1$ of length $n+1>0$. Then $x=yz$ where $y\in (L+M^\ast-\{\epsilon\})=\{L, M, M^2, ...\}, z\in L_1$ by definition. Since $z$ has at most $n$ characters, then $z\in L_2$ by induction. In addition, We can form $y$ from $(L+M)^\ast$, so $y\in L_2$. Can you do the rest? Mar 25, 2023 at 21:12
• @AspiringMat, I think I can't, I'm unfamiliar with those
– mark
Mar 26, 2023 at 8:20
• Unfamiliar with what? Mar 26, 2023 at 9:00

Informally, $$(L+M)^*$$ represents any sequence made of $$L$$s and/or $$M$$s, you can't make it more general. $$(L+M^*)^*$$ of course includes $$(L+M)^*$$, but the latter cannot be a proper subset.
$$L+M^*⊆(L+M)^*$$ so that
$$(L+M^*)^*⊆((L+M)^*)^*=(L+M)^*$$