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

  • $\begingroup$ Has been asked before, I believe. $\endgroup$ Dec 24, 2015 at 13:30
  • 2
    $\begingroup$ Was asked here, and compare with an empty product $\endgroup$
    – harold
    Dec 24, 2015 at 13:32

2 Answers 2


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

  • $\begingroup$ but then concatenation of non-zero words in $L$ with zero words in $\emptyset$ yields $\emptyset$ $\endgroup$
    – Mahesha999
    Dec 24, 2015 at 13:43
  • 2
    $\begingroup$ Which is why all other powers of $L$ are empty. $\endgroup$ Dec 24, 2015 at 13:43
  • $\begingroup$ 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 $\endgroup$
    – Mahesha999
    Dec 24, 2015 at 13:44
  • 1
    $\begingroup$ No, $LM=\emptyset$ if either of $L,M$ is empty. $\endgroup$ Dec 24, 2015 at 13:44
  • 3
    $\begingroup$ $\emptyset^n = \emptyset$ for $n > 0$. $\endgroup$ Dec 24, 2015 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.)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.