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?

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

1 Answer 1

Reset to default
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)^*$$

Improve this answer
$\endgroup$

Your Answer

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

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