4
$\begingroup$

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

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

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

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

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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