[Solved]: Why is the zero-th power of the empty set {ε}?

Problem Detail: 

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?

Asked By : lukas.coenig

Answered By : Raphael

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$

to

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60240

3.2K people like this

 Download Related Notes/Documents