[Solved]: Does the complement of sigma Kleene star exist?

Problem Detail: 

If $\Sigma^*$ is the set of ALL strings including the empty string, then what can its complement possibly be? The empty set?

Asked By : Daniel Baughman

Answered By : David Richerby

Yes, the complement of all possible strings¹ is no strings at all. A machine that decides $\Sigma^*$ accepts every input; a machine that decides the complement of $\Sigma^*$ rejects every input.

¹ Strictly speaking, all finite strings over some fixed alphabet $\Sigma$.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/30384