Kleene starKleeneStar2002-02-24 04:13:282009-08-04 20:41:56DefinitionKleene plus\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}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 \emph{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$.
\newcommand{\concat}{\ensuremath{+\hspace{-1ex}+}}
The definition of Kleene star can be generalized so that it operates on any
monoid $(M, \concat)$, where $\concat$ is a binary operation on the set $M$.
If $e$ is the identity element of $(M, \concat)$
and $S$ is a subset of $M$, then $S^*$ is the smallest superset of $S$ that
contains $e$ and is closed under $\concat$.
\subsubsection*{Examples}
\begin{itemize}
\item $\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^*$.
\item If $E=\lbrace \lambda \rbrace$, then $E^*=E$, since $\lambda a=a\lambda=a$ by definition, so $\lambda\lambda=\lambda$.
\item If $A=\lbrace a\rbrace$, then $A^*=\lbrace \lambda, a, aa, aaa, \ldots \rbrace$.
\item If $\Sigma = \left\{ a, b \right\}$, then $\Sigma^* = \left\{ \lambda, a, b, aa, ab, ba, bb, aaa, \dots \right\}$
\item If $S = \left\{ ab, cd \right\}$, then $S^* = \left\{ \lambda, ab, cd, abab, abcd, cdab, cdcd, ababab, \dots \right\}$
\end{itemize}
For any set $S$, $S^*$ is the free monoid generated by $S$.
\textbf{Remark}. There is an associated operation, called the \emph{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$.