What is the resulting set for {0,1}*\{0}*?

Question

If we have a language $L = \{0\}^*$ over the alphabet $\Sigma=\{0,1\}$, what is $\Sigma^*\backslash L$?

That's what I think:

$\{0,1\}^* = \{\epsilon, 0, 1, 00, 01, 10, 11, 000, 001, ... \}$
$\{0\}^* = \{\epsilon, 0, 00, 000, 0000, ... \}$
$\{0,1\}^*\backslash \{0\}^*= \{1,01,10,11,001,...\}$

In other words, the resulting set should contain everything from $\Sigma^*$ except the empty string and any string that contains 0s but not 1s.

If my thinking is correct, then how can I express $\{1,01,10,11,001,...\}$ more succinctly using set notation? I was thinking of something like $\{0,1\}^*\{1\}\{0,1\}^*$ but I'm not sure if it's correct or if there's a better way.

Answer 1

You are correct that the words not in $0^*$ are exactly those words which contain $1$ somewhere. You are also correct that you can represent this complement using the regular expression $(0+1)^*1(0+1)^*$. There are other regular expressions for the same language, for example $0^*1(0+1)^*$ (which is a "deterministic" regular expression).