Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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

share|improve this question
1  
The second one is "all ones or all zeroes", which doesn't include e.g. 0101010 –  vonbrand Feb 3 at 4:41
add comment

2 Answers

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|improve this answer
add comment
  (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|improve this answer
add comment

Your Answer

 
discard

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.