[Solved]: Kleene star operation on the empty language

Problem Detail: 

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

Asked By : Sagnik

Answered By : babou

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.

Best Answer from StackOverflow

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