4
$\begingroup$

In the book introduction to automata theory and languages, $L^*$ is defined as

$$L^* = \bigcup_{i=0}^\infty L^i $$

The book also says that $\emptyset^* = \{ \epsilon \}$. But since $\emptyset$ is the empty set

$$L^* = L^0 \cup L^1 \cup L^2 ... $$

$$= L^0 \cup \emptyset$$ -- since $ \emptyset\emptyset = \emptyset $ and there are 0 elements of $L$

Now since L is $ \emptyset $, then it does not contain $\epsilon$ either. So thus

$$L^* = \emptyset $$

But that does not seem to be the case. According to the book, $L^0$ is $\{ \epsilon \}$ and thus $L^* = \{ \epsilon \}$, for L = $\emptyset$. Where am I going wrong?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ That's a corner case that depends on the exact definition of $L^0$. In your case the definition seems to be $L^0=\epsilon$. I wouldn't worry about it. $\endgroup$ – Yuval Filmus Sep 14 '14 at 4:53
  • $\begingroup$ @YuvalFilmus Is there an ambiguity in definition of L^0? I thought it was just the set of all strings with length 0 contained in L. since L itself is $\Phi$, there are no strings of length 0, and thus L^0 must be $\Phi$ . $\endgroup$ – user21758 Sep 14 '14 at 4:59
  • $\begingroup$ No, $L^n$ is the set of concatenations of $n$ words from $L$. For example, $L^1=L$. $\endgroup$ – Yuval Filmus Sep 14 '14 at 5:03
  • 1
    $\begingroup$ $L^0$ is $\epsilon$. There is no ambiguity here; it has to be this way for the extension of concatenation from strings to languages to be a functor. $\endgroup$ – Pseudonym Sep 14 '14 at 9:18
  • $\begingroup$ @Pseudonym I do agree regarding $L^0$ when $L$ is not empty. But is it really important when $L=\emptyset$? See my answer for more details. I thought you might have comments. $\endgroup$ – babou Sep 15 '14 at 1:29
5
$\begingroup$

You are correct with $L^* = L^0 \cup \emptyset$.

But $L=\emptyset$ does not imply $L^0 = \emptyset$. Consider $L^i$ to be built incrementally: You start with $\epsilon$ and then add a word from $L$ to the end $i$ times.

If $i\ge 1$ and $L=\emptyset$, this will fail when you try to add the first word, since there are no words in $L$. So here $L^i$ becomes $\emptyset$. But for $L^0$ you never try to take a word from $L$. So the fact that $L$ is empty does not matter, you simply terminate after initialising your word as $\epsilon$.

Thus $L^0=\{\epsilon\}$ and $L^* = \{\epsilon\} \cup \emptyset = \{\epsilon\}$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ For another way of looking at it, note that $a^0 = \varepsilon$ (in strings) makes as much sense as $5^0 = 1$ (in the reals) -- the empty word is the neutral element in the free monoid that is $(\Sigma^*, \cdot)$. $\endgroup$ – Raphael♦ Sep 15 '14 at 10:55
  • $\begingroup$ @Raphael Yes. But $0^0$ is undefined, and that makes $\emptyset^0=\{\varepsilon\}$ somewhat suspcious. I develop the point in my answer (just updated). $\endgroup$ – babou Sep 15 '14 at 13:11
  • $\begingroup$ @babou At the risk of stretching the analogy, $0^0$ would correspond to $\emptyset^{\emptyset}$, which is indeed undefined. $\endgroup$ – Raphael♦ Sep 15 '14 at 14:22
  • $\begingroup$ @Raphael Your analogy has no mathematical foundation that I can see. As explained in my answer, I am considering two models of the same abstract algebra, the semiring, where the concept of multiplicative powers of an element can be defined abstractedly, and correspond to a morphism from the semigroup (N,+). The models have respectively 0 and ∅ for additive identity, and the issue is the meaning of the null power of each. Since the first model keeps $0^0$ undefined, you cannot expect any compelling argument, based only the the semiring axioms, to give meaning to $\emptyset^0$ in the second. $\endgroup$ – babou Sep 15 '14 at 18:03
4
$\begingroup$

In a nutshell

It is easy to show why we should define $L^0=\{\varepsilon\}$ when $L$ is not empty.

However, the definition $\emptyset^0=\{\varepsilon\}$, though nicely consistent, and probably convenient in many cases, could be just arbitrary. It might even be that not defining it should be wiser.

Why $L^0=\{\varepsilon\}$ when $L$ is not empty ?

The proper answer is the one given, maybe too abstractedly, by Pseudonym's comment.

The point is that you are asking for the meaning of a notation. The meaning of a notation is whatever the mathematician chooses it to be.

But mathematicians do not do that randomly. They use notations that make things look simple and consistent.

The power notation is often used in mathematics to mean repetition, when dealing with an associative operation (i.e. with a semigroup). The concatenation of languages, here noted explicitly $\bullet$ for clarity, is associative. Hence, we can use the power notation to represent the concatenation of a language $L$ with itself, with $L^1=L$, $L^2=L\bullet L$, $L^3=L\bullet L\bullet L$, and so on, or more generally: $L^{n+1}= L^n\bullet L$.

An interesting aspect of this is that exponents behave exactly as they do for usual exponentiation of numbers: $L^{a+b}=L^a\bullet L^b$ for any pair of positive integer $a$ and $b$.

This shows that there is a morphism from (the semigroup of) the positive integers $\mathbb N_+$ with addition to (the semigroup of) the powers of any language $L$ with concatenation.

It you now decide to extend the power notation to exponent $0$, you want to preserve as much as possible these morphisms, so as to keep your mathematics consistent. The integer $0$ is the neutral element that extends the additive semigroup of positive integer $\mathbb N_+$ into the additive monoid of non-negative integers $\mathbb N_0$.

Hence, to preserve the morphism, you want $L^0$ to denote the neutral element for the concatenation of languages. This neutral element is the language $\{\varepsilon\}$, containing only the empty string, since for any language $L$, we have the relations $L\bullet\{\varepsilon\}=\{\varepsilon\}\bullet L=L$.

Hence, we choose to define, for any language $L$, $L^0=\{\varepsilon\}$

Using this definition, the identity $L^{a+b}=L^a\bullet L^b$ remains true even when $a$, or $b$, or both become 0. And it is the only way to achieve that as noted by Pseudonym in his comment.

But what about $\emptyset^0$ ?

For consistency (again) across languages, this definition should apply to all, including the empty language $\emptyset$. But this argument is not too compelling in the case of $\emptyset$, even though defining $\emptyset^0=\{\varepsilon\}$ raises no consistency problem that I know of.

My misgivings about this definition relate to the fact that languages over an alphabet $\Sigma$ actually form a semiring, and the empty language $\emptyset$ is the neutral element of the commutative monoid (for set union) of that semiring. The non-negative integers $\mathbb N_0$ with addition and multiplication also form a semiring. The power notation is also available (for repeted multiplications). But defining $0^0$ is, to say the least, a risky business, at least when considering the integers as part of larger theories. Hence, I tend to be cautious regarding $\emptyset^0$.

If one considers the axiomatisation of the semiring of languages, such as given by an answer by Pseudonym to another question, or by the semiring axioms in wikipedia, it does not seem possible to deduce anything about $\emptyset^0$ from these axioms. Actually, they cannot provide a definition for it, since this has apparently to be undefined in some models of the theory.

People seem to have found many arguments to justify that $0^0$ should be $1$, but there are also compelling reasons to have it undefined: the function $\lambda x.y. x^y$ is not continuous at the origin. I am wondering whether the argument given in FrankW's answer, and my own consistency argument above, do not run the risk of being similarly disputable.

Transposing the arguments from the semiring of languages to the semiring of non-negative integers

My consistency argument is also valid in the semiring $(\mathbb N_0,+, \times)$ of non-negative integers with addition and multiplication, where the power notation is also used to indicate repeated product, with the possible definition: $\forall a\in \mathbb N_0, \forall i\in \mathbb N_+, a^1=a\wedge a^i+1=a^i\times a$.

Then we also have the natural extension from the multiplicative semigroup to a monoid with a neutral element $1$, so that we define $\forall a\in \mathbb N_0, a^0=1$. And the same consistency argument I suggested for $\emptyset^0$ would then apply to chose to define $0^0=1$.

This goes also for the argument in FrankW's answer. In the semiring $(\mathbb N_0,+, \times)$, when defining $a^i$, you start with 1 and then you multiply by $a$ repeatedly $i$ times. But if $i=0$, you just stay with 1, and multiply $0$ times by $a$. Hence $a^0=1$. And when $a=0$, since you do not even need to consider $a$ for product, the result is the same. Hence $0^0=1$.

So both our reasonning apply in the case of the semiring $(\mathbb N_0,+, \times)$, and give the same result: $0^0=1$. But this result is considered wrong for numbers, where $0^0$ should remain undefined (I might be worthwhile investigating deeper the known reasons).

An unconclusive conclusion

Actually, the Kleene plus operation, which some people found necessary to define does not need to consider $L^0$: $$ V^+=\bigcup_{i \in \mathbb N_+} V^i = V^1 \cup V^2 \cup V^3 \cup \ldots$$

The Kleene star could be defined by adding the empty word $\varepsilon$.

When looking at Kleene algebra (in wikipedia) it seems that the power notation does not play a major role, and I did not see anything that requires defining $\emptyset^0$. But I am no expert on Kleene algebras.

So I have to finish with questions I cannot answer:

  • is it really important to define $\emptyset^0=\{\varepsilon\}$, beyond the advantage of consistency with non-empty languages ?

  • is it really important to define $\emptyset^0$ at all ?

  • would it be inconsistent, or problematic, or possibly useful, to define $\emptyset^0=\emptyset$ ?

  • could there be compelling reasons to leave $\emptyset^0$ undefined ?

|cite|improve this answer
$\endgroup$
  • $\begingroup$ The only thing I have to add to your excellent answer is "yes, it's important". If $\emptyset^0$ is not defined, then you don't have a Kleene algebra. $\endgroup$ – Pseudonym Sep 15 '14 at 3:04
  • $\begingroup$ @Pseudonym That did not appear obvious to me, as I looked at Kleene algebras (I never really worked with them as such). Could you make your statement more precise? $\endgroup$ – babou Sep 15 '14 at 13:15

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.