patternMinor
Kleene closure of the empty set
Viewed 0 times
theemptykleeneclosureset
Problem
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?
$$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?
Solution
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\}$.
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\}$.
Context
StackExchange Computer Science Q#29985, answer score: 5
Revisions (0)
No revisions yet.