In the context of regular languages is Ø* = Ø?

51 Views Asked by At

In the context of regular expressions is Ø* = Ø? and why?

1

There are 1 best solutions below

1
On BEST ANSWER

$\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).