Kleene star

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$ . $^*$ is also called the asterate.

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

The definition of Kleene star can be generalized so that it operates on any monoid , where is a binary operation on the set $M$ . If $e$ is the identity element of and $S$ is a subset of $M$ , then $S^*$ is the smallest superset of $S$ that contains $e$ and is closed under .

Examples

• $\varnothing^*=\lbrace \lambda \rbrace$ , since there are no strings of finite length consisting of symbols in $\varnothing$ , so $\lambda$ is the only element in $\varnothing^*$ .
• If $E=\lbrace \lambda \rbrace$ , then $E^*=E$ , since $\lambda a=a\lambda=a$ by definition, so $\lambda\lambda=\lambda$ .
• If $A=\lbrace a\rbrace$ , then $A^*=\lbrace \lambda, a, aa, aaa, \ldots \rbrace$ .
• If $\Sigma = \left\{ a, b \right\}$ , then $\Sigma^* = \left\{ \lambda, a, b, aa, ab, ba, bb, aaa, \dots \right\}$
• If $S = \left\{ ab, cd \right\}$ , then $S^* = \left\{ \lambda, ab, cd, abab, abcd, cdab, cdcd, ababab, \dots \right\}$

For any set $S$ , $S^*$ is the free monoid generated by $S$ .

Remark. There is an associated operation, called the Kleene plus, is defined for any set $S$ , such that $S^+$ is the smallest set containing $S$ such that $S^+$ is closed under the concatenation. In other words, $S^+=S^*-\lbrace \lambda\rbrace$ .