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

How do I prove it is wrong?

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

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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