17
$\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$?

Improve this question
$\endgroup$
5
  • 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
    Commented Jul 31, 2015 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
    Commented Jul 31, 2015 at 15:35
  • $\begingroup$ Simply because $\varepsilon \in L^0 = \{\varepsilon\}$ for all $L$, by definition. $\endgroup$
    – Raphael
    Commented Jul 31, 2015 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
    Commented Jul 31, 2015 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
    Commented Jul 31, 2015 at 16:44

2 Answers 2

Reset to default
16
$\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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ This answer cleared all my doubts. And the links were excellent. $\endgroup$
    – Sagnik
    Commented Jul 31, 2015 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.

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jul 31, 2015 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
    Commented Jul 3, 2018 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
    Commented Jul 3, 2018 at 5:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.