It has been asked before why $\emptyset^\star=\{\epsilon\}$. The answer boils down to $\emptyset^\star$ being defined as $$ L^\star = \bigcup_{i=0}^\infty L^i, $$ where a word in $L^i$ is the concatenation of $i$ words from $L$. So, for the empty language this leaves empty sets for all $i>0$, "but $L^0 = \{ \epsilon \}$ since $\epsilon$ is the concatenation of zero words from $L$. It doesn't matter if $L$ is empty or not, since we are choosing zero words from $L$." (quoted from the answer.)

And that's what I'm curious about: is there a good reason to say that the concatenation of zero words is $\epsilon$ even for the empty set? Can you compare it to $0^0=1$ in arithmetics (where it's just more or less arbitrary) or is there a strong logical reason for this to be true?

  • 2
    $\begingroup$ This is discussed in Yuval's answer there and comments on it; what more do you want? $\endgroup$
    – Raphael
    Jul 2 '16 at 15:56
  • $\begingroup$ You're right, I didn't see the second answer - sorry! $\endgroup$ Jul 2 '16 at 16:30

Strings with concatenation and the empty word form a monoid.

In monoids, the empty concatenation/sum/product yields the neutral element, i.e. $\varepsilon$/0/1.

An empty concatenation does not need any words to start with, so $\emptyset^0 = \{\varepsilon\}$.

Intuitively, if you specialize

$L^n$ is the set of all words obtained by $n$-fold concatenation of words in $L$


$L^0$ is the set of all words obtained by zero concatenations (of words in $L$)

you can just stop reading after "concatenations" and the contents of $L$ do not matter; we don't even need it to be non-empty.

  • 1
    $\begingroup$ N.B. the only reason this argument does not apply with equal force to justify $0^0 = 1$ is that exponentiation is not a monoid. $\endgroup$
    – zwol
    Jul 2 '16 at 21:29
  • 2
    $\begingroup$ @zwol: I don't think you've quite thought that through. Neither $L^n$ nor $m^n$ is a monoid operation. Raphael is using $L^n$ to denote repeated application of a monoid operation (namely concatenation); if you use $m^n$ the analogous way (to denote repeated multiplication), then $0^0 = 1$ is actually correct. The reason this argument doesn't apply to $0^0$ in general is that $x^y$ doesn't always denote repeated multiplication; $0^{0.1}$ (for example) has no monoid-related interpretation, and $\lim\limits_{x\to 0}0^x \ne 1$. $\endgroup$
    – ruakh
    Jul 2 '16 at 22:54

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.