4
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ The second one is "all ones or all zeroes", which doesn't include e.g. 0101010 $\endgroup$
    – vonbrand
    Feb 3, 2014 at 4:41

2 Answers 2

11
$\begingroup$

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^*$?

$\endgroup$
0
$\begingroup$
  (1*+0*)= 11.. or 00... but cannot produce 101010101
  (1+0)*= anything with 1 and 0

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

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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