1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Your question already includes a complete answer to the original problem but no question about this answer. Thus, only "yes/no" answers may remain, helping neither you nor future visitors. Please read related meta discussions here and here and adjust your question accordingly, e.g. by formulating a specific question about a single element of your answer you are uncertain about. If you just want general feedback, you are welcome to visit us in Computer Science Chat. $\endgroup$ – David Richerby Mar 29 '16 at 1:10
5
$\begingroup$

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).

$\endgroup$

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.