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^xemptyset=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 $Wneqemptyset$ 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^0cupemptyset^1cupemptyset^2cupldots \ &={epsilon}cupemptysetcupemptysetcupldots\ &={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
