Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I know that (1 + 0)* is the set of all bit strings; but isn't 1* + 0* the same thing?

share|cite|improve this question
The second one is "all ones or all zeroes", which doesn't include e.g. 0101010 – vonbrand Feb 3 '14 at 4:41
up vote 11 down vote accepted

The set $1^*+0^*$ is composed of two parts: $1^*$ and $0^*$. The first part, $1^*$, is all strings composed entirely of $1$s. The second part, $0^*$, is all strings composed entirely of $0$s. In contrast, $(1+0)^*$ is all strings composed of $0$s and $1$s. Can you now think of a string in $(1+0)^*$ but not in $1^*+0^*$?

share|cite|improve this answer
  (1*+0*)= 11.. or 00... but cannot produce 101010101
  (1+0)*= anything with 1 and 0

yeah: (1*+0*)* would be a different story.

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.