Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The articles and textbooks mention that,

$\emptyset^\star = \{\epsilon\}$

The star operation puts together any number of strings from the language to get a string in the result. If the language is empty, the star operation can put together 0 strings, giving only the empty string.

(Taken from page 65 of the above mentioned textbook.)

Now the logic behind this somewhat escapes me. How come a null set when taken zero times can give you an empty string?

To begin with, a null set has only zero strings. But a set with an empty string has one string with zero length.

Could somebody please explain this with real life examples?

share|improve this question

1 Answer 1

up vote 4 down vote accepted

By definition, the strings in $X^*$ (for any language $X$, whether $X = \emptyset$ or not) are those constructed by taking some finite number (possibly 0) of strings from $X$ and concatenating them.

If you take 0 strings and concatenate them, you get $\epsilon$. Note that this has nothing to do with whether $X=\emptyset$ or not. The empty string $\epsilon$ is always in $X^*$ regardless of what $X$ is.

When $X = \emptyset$, there are no other strings in $X^*$, because you cannot take more than 0 strings from $\emptyset$. So the only string in $\emptyset^*$ is $\epsilon$: thus $\emptyset^* = \{\epsilon\}$.

Now let $X$ be some nonempty language, say $X = \{a\}$. Then $X^* = \{\epsilon, a, aa, aaa, aaaa, \ldots\}$. Notice that $\epsilon$ is still in $X^*$, but now there are other strings because I can concatenate one or more $a$'s together. The $\epsilon$ is what I get by concatenating zero $a$'s.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.