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$ – Yuval Filmus Jun 30 '18 at 21:29
  • $\begingroup$ @YuvalFilmus and how do I prove it wrong? $\endgroup$ – denis631 Jul 1 '18 at 9:51
  • $\begingroup$ You find a counterexample. $\endgroup$ – Yuval Filmus Jul 1 '18 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.

| cite | improve this answer | |

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.