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 strings1 is no strings at all. A machine that decides $Sigma^*$ accepts every input; a machine that decides the complement of $Sigma^*$ rejects every input. 1 Strictly speaking, all finite strings over some fixed alphabet $Sigma$.
Best Answer from StackOverflow
Question Source : http://cs.stackexchange.com/questions/30384
