11
$\begingroup$

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?

$\endgroup$
20
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ "When X=∅, there are no other strings in X∗, because you cannot take more than 0 strings from ∅. " -But, when X = {}, then X* should be X0 U X1 U X2 U.... We know that X0 is {} for any language. And, X1 = X = {}. Since X is an empty language so, any power of X will not generate any language. So, how come X* equals {eplison)? Correct me, please. $\endgroup$ – Palak Jain Jul 3 '18 at 4:12
  • 2
    $\begingroup$ "We know that X0 is {} for any language": No! $X_0 = \{ \epsilon \}$ for any language, because concatenating 0 strings produces the empty string. $\endgroup$ – Ted Jul 7 '18 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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