PlanetMath (more info)
 Math for the people, by the people.
Encyclopedia | Requests | Forums | Docs | Wiki | Random | RSS  
Login
create new user
name:
pass:
forget your password?
Main Menu
Kleene star (Definition)

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

The definition of Kleene star can be generalized so that it operates on any monoid $ (M, \ensuremath{+\hspace{-1ex}+})$, where $ \ensuremath{+\hspace{-1ex}+}$ is a binary operation on the set $ M$. If $ e$ is the identity element of $ (M, \ensuremath{+\hspace{-1ex}+})$ and $ S$ is a subset of $ M$, then $ S^*$ is the smallest superset of $ S$ that contains $ e$ and is closed under $ \ensuremath{+\hspace{-1ex}+}$.

Examples


$\displaystyle \Sigma = \left\{ a, b \right\}$   $\displaystyle \Sigma^* = \left\{ \lambda, a, b, aa, ab, ba, bb, aaa, \dots \right\}$  
$\displaystyle S = \left\{ ab, cd \right\}$   $\displaystyle S^* = \left\{ \lambda, ab, cd, abab, abcd, cdab, cdcd, ababab, \dots \right\}$  



"Kleene star" is owned by Logan.
(view preamble)

View style:

See Also: alphabet, string, regular expression, Kleene algebra, language, convolution, weight (strings), weight enumerator


Cross-references: subset, identity element, binary operation, monoid, generated by, operation, closed under, contains, superset, empty string, length, finite, strings, alphabet
There are 4 references to this entry.

This is version 2 of Kleene star, born on 2002-02-24, modified 2002-05-03.
Object id is 2584, canonical name is KleeneStar.
Accessed 3897 times total.

Classification:
AMS MSC68Q70 (Computer science :: Theory of computing :: Algebraic theory of languages and automata)
 20M35 (Group theory and generalizations :: Semigroups :: Semigroups in automata theory, linguistics, etc.)

Pending Errata and Addenda
None.
Discussion
Style: Expand: Order:
forum policy

No messages.

Interact
rate | post | correct | update request | add derivation | add example | add (any)