In the context of regular expressions is Ø* = Ø? and why?
Asked
Active
Viewed 50 times
0
-
Please try to add more context. – tc216 Feb 10 '17 at 00:38
-
What does that symbol mean here? – copper.hat Feb 10 '17 at 00:48
-
@copper.hat That's the Kleene star operator, which is standard notation in this context. (Incidentally: to the OP, your question is answered in the third example at the page linked in my previous sentence!) – Noah Schweber Feb 10 '17 at 01:29
-
@jeff I appreciate your wanting to answer, but the context is regular expressions, the question was answered below correctly. – j doe Feb 10 '17 at 21:26
-
@jdoe okay then :) – tc216 Feb 10 '17 at 23:42
1 Answers
2
$\Sigma^*$ is the set of all finite strings, each of whose terms is from $\Sigma$ . . . so the answer is no!
The empty string, $\epsilon$, is an element of $\emptyset^*$: all of its terms are in $\emptyset$, because there aren't any. This is an instance of a more general phenomenon: universal statements always hold of the emptyset. For example, every element of the emptyset (or term of the emptystring) is a pink elephant.
And it's not hard to see that $\epsilon$ is the only element of $\emptyset^*$ (any string other than $\epsilon$ has at least one term - well, we can't have that here!). So $\emptyset^*=\{\epsilon\},$ which is not the same thing as $\emptyset$ (for the same reason that $\{\emptyset\}\not=\emptyset$; see e.g. here).
Noah Schweber
- 245,398
-
Thank you! This makes tons of sense, and in hind-site I should have realized. Great answer. – j doe Feb 10 '17 at 20:58