15
$\begingroup$

In my text book it is mentioned that: $\emptyset^*=\{\epsilon\}$ where $\emptyset$ is an empty language.

However, we know that $L \cdot \emptyset = \emptyset$, where $L$ is any Language.

I am not able to intuitively grasp this concept because the Kleene star operation points towards the fact that $\emptyset^*=\emptyset^0 \cup \emptyset^1 \cup \emptyset^2 \cup \cdots$ .

So why is $\emptyset^*$ not equal to $\emptyset$?

$\endgroup$
  • 3
    $\begingroup$ See this answer. Basically, for any non-empty set $W$, $W^0=\emptyset$ for consistency of the formula $W^xW^y=W^{x+y}$. This is extended to the case when $W=\emptyset$ as the more natural extension. This is the usual choice in semi-rings. The rest follows from the definition of the Kleene star. $\endgroup$ – babou Jul 31 '15 at 15:26
  • $\begingroup$ However, for numbers, $0^0$ is left undefined , mostly because of continuty issues as I recall, though it may often be convenient to define it equal to $1$. See $0^0$ $\endgroup$ – babou Jul 31 '15 at 15:35
  • $\begingroup$ Simply because $\varepsilon \in L^0 = \{\varepsilon\}$ for all $L$, by definition. $\endgroup$ – Raphael Jul 31 '15 at 16:02
  • $\begingroup$ @Raphael Yes. You can put it that way. But it is arbitrary, afaik, when $L=\emptyset$. I should probably write my answer differently. I try too hard to explain,. $\endgroup$ – babou Jul 31 '15 at 16:14
  • $\begingroup$ @babou In the end, every definition is arbitrary. Some definitions are helpful, others are not. Imho, trying to find intuition in definitions as basic as this is rarely helpful, and sometimes harmful. $\endgroup$ – Raphael Jul 31 '15 at 16:44
13
$\begingroup$

If you consider now the powers of a language $W$ you have $W^xW^y=W^{x+y}$ If you want this to be consistent over $\mathbb N_0$, i.e. the non-negative integers, you have to define $W^0=\{\epsilon\}$. If you took it to be $\emptyset$ you would have $W^x=W^{x+0}=W^xW^0=W^x\emptyset=\emptyset$ including, among others, for $x=1$. Thus we would have $W^1=W=\emptyset$ for any $W$. Thus this would clearly be inconsistent. A similar inconsistency arises for any other choice than $\{\epsilon\}$, which is the identity for language concatenation.

Hence, the only consistent consistent definition of $W^0$ for a non empty set $W$ is $W^0=\{\epsilon\}$.

It is then convenient to extend the definition to the case when $W=\emptyset$ as $\emptyset^0=\{\epsilon\}$.

This is just a consistent and convenient definition, often adopted in semi-rings but it cannot be proved, unlike thw case when $W\neq\emptyset$ where there is no other consistent definition.

However, other definitions have then to be given in a consistent way, which implies that

$$\begin{align} \emptyset^*&=\emptyset^0\cup\emptyset^1\cup\emptyset^2\cup\ldots \\ &=\{\epsilon\}\cup\emptyset\cup\emptyset\cup\ldots\\ &=\{\epsilon\} \end{align}$$

The topic is discussed on many web pages. In the case of the semi-ring of numbers (the lack of precision is intentional) this is discussed at length on this page: Zero to the zero power - Is $0^0=1$?.

The semi-ring of languages is described in this answer.

$\endgroup$
  • $\begingroup$ This answer cleared all my doubts. And the links were excellent. $\endgroup$ – Sagnik Jul 31 '15 at 16:53
3
$\begingroup$

The concatenation of zero words from $\emptyset$ is the empty word $\epsilon$, so $\epsilon \in \emptyset^*$. More generally, for a language $L$, the Kleene star $L^*$ consists of all concatenation of any number of words from $L$, any number including zero words.

$\endgroup$
  • $\begingroup$ I was looking for a more mathematical explanation because I was not being able to get an intuitive understanding of the concept of "concatenation of zero words". However after reading @babou's answer and this answer all my doubts got cleared. Thank you. $\endgroup$ – Sagnik Jul 31 '15 at 16:56
  • $\begingroup$ "...for a language L, the Kleene star L* consists of all concatenation of any number of words from L, any number including zero words" Here, how does zero number of words imply eplison? epsilon is a word, so how can we say that zero number of words include epsilon? Correct me, please. $\endgroup$ – Palak Jain Jul 3 '18 at 5:03
  • $\begingroup$ The concatenation of zero words is the neutral element for concatenation, which is the empty word. In the same way, the sum of zero elements is zero, the product of zero elements is one, the union of zero sets is the empty set, and so on. $\endgroup$ – Yuval Filmus Jul 3 '18 at 5:06

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.