The definition of the Kleene star is separated into two cases [1] [2]:

If $\Sigma$ is an alphabet (a set of symbols), then the Kleene star of $\Sigma$, denoted $\Sigma^*$, is the set of all strings of finite length consisting of symbols in $\Sigma$, including the empty string $\lambda$.

If $S$ is a set of strings, then the Kleene star of $S$, denoted $S^*$, is the smallest superset of $S$ that contains $\lambda$ and is closed under the string concatenation operation. That is, $S^*$ is the set of all strings that can be generated by concatenating zero or more strings in $S$.

Question: why do we separate the definition into two distinct cases? How is one definition different than the other?

  • 2
    $\begingroup$ It's subtle. Basically the first definition, suitably formalized, tells you what a string is, and you need to know what strings are for the second definition to make sense. $\endgroup$ – Qiaochu Yuan Nov 24 '17 at 21:25

Both definitions are a special instance of a more general definition. Given a subset $S$ of a monoid $M$, $S^*$ denotes the submonoid of $M$ generated by $S$. If $S$ is a set of words, i.e. a subset of the free monoid on $A$, you recover your second definition. Moreover, if $S = A$, then $S^*$ is the free monoid on $A$, which justifies the first notation: the set of all words on the alphabet $A$ is denoted $A^*$.


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.