4
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ The second one is "all ones or all zeroes", which doesn't include e.g. 0101010 $\endgroup$ – vonbrand Feb 3 '14 at 4:41
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^*$?

| cite | improve this answer | |
$\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.

| cite | improve this answer | |
$\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.