Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
It's an exercise question from chapter 0 of Michael Sipser's book Introduction to the Theory of Computation.
e. The set containing the empty string
f. The set containing nothing at all
I guess the empty string is still something, which is not nothing. Would this be the difference?
Yes, that's it.
One important difference could be seen using concatenation: let $L$ be any nonempty language.
Then $\{\varepsilon\}L = L$, but $\emptyset L = \emptyset$. Clearly those are different.
The difference is essentially structural.
In the case of the set containing the empty string, the set has a length of 1.
In the case of the set containing nothing, the set has a length of 0.
A string is typically conceived as a container of characters (as opposed to say an int, which is not typically conceived as a container of numbers or bits).
The string, as a container, can be present, but contain no characters - the string can have length 0, even though the set which contains the string has length 1.
In this way, there are two levels of containment when talking of sets containing strings, and what the set contains is not to be conflated with what the string contains.
This is distinct from "nothing" in the set, which is where even the string-as-a-container is absent from the set.
It might have been slightly clearer if Sipser had phrased himself as:
e. The set containing the empty string.
f. The set that doesn't contain anything.
A general way to check if two sets are equal: two sets $S_1$ and $S_2$ are equal if (i) all of the elements in $S_1$ are in $S_2$, and (ii) all of the elements in $S_2$ are in $S_1$. This property is called "extensionality".
In your case, let's apply the definition. Our first set, $S_1$ is the set containing the empty string $\epsilon$. Our second set, $S_2$ is the empty set. To check property (i), we look at all elements in $S_1$: that's just one element, $\epsilon$. But $\epsilon$ is not in $S_2$, since $S_2$ is the empty set (and thus contains no elements). So the two sets are not equal.
Think of the set containing the empty string as one, and the empty set as zero.
A Kleene algebra is essentially an idempotent semi-ring, plus the Kleene closure operator. Ignoring the Kleene closure (a.k.a. Kleene star) operator, the ordered "multiplication" corresponds to string concatenation and "addition" corresponds to set union. Most of the axioms should look very familiar:
$$\begin{eqnarray*} a + (b + c) & = & (a + b) + c \\ a \cdot (b \cdot c) & = & (a \cdot b) \cdot c \\ a + b & = & b + a \\ a\cdot (b + c) & = & a \cdot b + a \cdot c \\ (b + c) \cdot a & = & b \cdot a + c \cdot a \\ 0 + a & = & a + 0 = a \\ 1 \cdot a & = & a \cdot 1 = a \\ 0 \cdot a & = & a \cdot 0 = 0 \end{eqnarray*}$$
Those last three show the difference between the empty set ($0$) and the set containing the empty string ($1$): the empty set is the identity for set union, and the empty string is the identity for string concatenation. The empty set also annihilates string concatenation.
That's a lot of terminology, but I think it's much easier to understand if you write it in this algebraic notation, rather than in regular expression notation:
$$\begin{eqnarray*} \emptyset \,|\,a & = & a\,|\,\emptyset = a \\ \epsilon a & = & a \epsilon = a \\ \emptyset a & = & a \emptyset = \emptyset \end{eqnarray*}$$
Just for completeness, the thing that makes addition correspond to set union is that it is idempotent:
$$a + a = a$$
All of the other axioms of a Kleene algebra define the Kleene closure operator ${}^*$, which is important, but isn't relevant to your question. See the link above if you're interested.
It might be clearer to ask yourself whether a set containing an empty set is the same as an empty set. Russell and Whitehead say, "No."
