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 $ emptysetemptyset = 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 $ige 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
