# How is $\emptyset^* = \{\epsilon\}$?

I know that $$\emptyset$$ is a an empty language, i.e. language containing no string.

A law involving empty language is:

$$\emptyset L = L\emptyset = \emptyset$$

It correctly states that we cannot concatenate non empty language $$L$$ with a language $$\emptyset$$ containing no string (as their is no string to concatenate in $$\emptyset$$), it yields empty language.

Then how concatenating a language containing no string with itself any number of times can yield even empty string? That is, how following law exist:

$$\emptyset^* = \{\epsilon\}$$

• Has been asked before, I believe. – Yuval Filmus Dec 24 '15 at 13:30
• Was asked here, and compare with an empty product – harold Dec 24 '15 at 13:32

For any language $L$, by definition $$L^* = \bigcup_{i=0}^\infty L^i,$$ where a word in $L^i$ is the concatenation of $i$ words from $L$. In particular, $L^0 = \{ \epsilon \}$ since $\epsilon$ is the concatenation of zero words from $L$. It doesn't matter if $L$ is empty or not, since we are choosing zero words from $L$.

• but then concatenation of non-zero words in $L$ with zero words in $\emptyset$ yields $\emptyset$ – anir123 Dec 24 '15 at 13:43
• Which is why all other powers of $L$ are empty. – Yuval Filmus Dec 24 '15 at 13:43
• So it really requires both languages to be empty to yield empty string. If any one of them is non-empty, it will yield empty language – anir123 Dec 24 '15 at 13:44
• No, $LM=\emptyset$ if either of $L,M$ is empty. – Yuval Filmus Dec 24 '15 at 13:44
• $\emptyset^n = \emptyset$ for $n > 0$. – Yuval Filmus Dec 24 '15 at 13:48

$L^*$ can be defined as the smallest language satisfying the recursive equation

$$L^* = \{\epsilon\} \cup L L^*$$

or, equivalently as the the least fixed point of the (monotonic, Scott-continuous) language-valued function

$$f(M) = \{\epsilon\} \cup L M$$

over the complete lattice of languages (hence, by Tarski, such a fixed point exists).

The above definition may look quite abstract, but one can find it quite natural when comparing it to the usual definition of lists in functional languages as a recursive type:

data List l = Nil | Cons l (List l)


From the equation above, we can see that $\epsilon \in L^*$ is trivially true whatever is $L$. (Not unlike the empty list being a list of l, whatever type l is.)