patternMinor
Why is the zero-th power of the empty set {ε}?
Viewed 0 times
whytheemptypowerzeroset
Problem
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?
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?
Solution
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.
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.
Context
StackExchange Computer Science Q#60240, answer score: 6
Revisions (0)
No revisions yet.