HiveBrain v1.2.0
Get Started
← Back to all entries
gotchaModerate

Difference between 1* + 0* and (1 + 0)*

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
anddifferencebetween

Problem

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

Solution

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

Context

StackExchange Computer Science Q#20235, answer score: 11

Revisions (0)

No revisions yet.