# Regularity under set difference

Let L be a regular language. Then $\Sigma^{*} \backslash L^{*} = (\Sigma^{*} \backslash L)^{*}$

How do I prove it is wrong?

• You can't prove it, since it's wrong. Jun 30, 2018 at 21:29
• @YuvalFilmus and how do I prove it wrong? Jul 1, 2018 at 9:51
• You find a counterexample. Jul 1, 2018 at 9:54

For instance, take $\Sigma=\{a,b\}$ and $L=\{a\}$.
Then, $L^*=\{\epsilon,a,aa,\ldots\}$ and $\Sigma^*\setminus L^*$ comprises any word except those made by only $a$s. In other terms, those words containing at least one $b$.
Instead $(\Sigma^*\setminus L)$ comprises any words except $a$ (this includes $aa$, for instance). So, $(\Sigma^*\setminus L)^*$ comprises all concatenations of words which are not $a$. Well, this is the same set of words: all the words except $a$.
Concluding, it is easy to see that $aa$ belongs to the latter set but not the first one.
Not only we can find a counterexample, but we can even prove that the equation is false whatever $L$ is! Indeed, the empty word $\epsilon \in (\Sigma^*\setminus L)^* \setminus (\Sigma^*\setminus L^*)$ is a wtiness to their difference.