Need to separate Kleene star definition into two cases

300 Views Asked by At

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?

1

There are 1 best solutions below

0
On BEST ANSWER

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