Prove a relation . languages

57 Views Asked by At

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 \}$$

1

There are 1 best solutions below

0
On

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\}$.