[Solved]: Kleene closure of the empty set

Problem Detail: 

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?

Asked By : user21758

Answered By : FrankW

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\}$.

Best Answer from StackOverflow

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