0
$\begingroup$

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?

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Mar 25, 2023 at 21:12
  • $\begingroup$ @AspiringMat, I think I can't, I'm unfamiliar with those $\endgroup$
    – mark
    Mar 26, 2023 at 8:20
  • $\begingroup$ Unfamiliar with what? $\endgroup$ Mar 26, 2023 at 9:00

1 Answer 1

0
$\begingroup$

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.


More rigorously,

$$L+M^*⊆(L+M)^*$$ so that

$$(L+M^*)^*⊆((L+M)^*)^*=(L+M)^*$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.