Prove a relation . languages

Question

Consider an alphabet $\Sigma$ and languages $L_1,ドル $L_2$. I am trying to prove that $$(L_1 − L_2)^* = (L_1^* − L_2^*)^*$$ ($-$ is the difference). I suppose that $L_1= \{a\}$ and $L_2= \{b\}$. Then

$(L_1 − L_2)^* = \{a\}^* = \{\varepsilon, a, aa, aaa, \ldots \}\ $ and

$(L_1^* − L_2^*)^* = \{a, aa, aaa, \ldots \}^*$.

So the relation is true: $(L_1 − L_2)^* = (L_1^* − L_2^*)^*$

How I can prove it with definition? I only know that $$A\setminus B = \{x \mid x \in A \text{ and } x \notin B \}$$

• ghosts_in_the_code: There's a separate SE for theoretical computer science (though your question might be acceptable here also).
• J.-E. Pin: @ghosts-in-the-code This question would immediately be rejected on cstheory.stackexchange.com: this is not a research level question. In any case, never ask a question on several sites at the same time.

Answer 1

This is not true. Take $L_1 = \{a, aa\}$ and $L_2 = \{a\}$. Then $(L_1 - L_2)^* = (aa)^*$ but $(L_1^* − L_2^*)^* = (a^* - a^*)^* = \emptyset^* = \{\varepsilon\}$.