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
sections
Encyclopædia
Papers
Books
Expositions

meta
Requests (204)
Orphanage
Unclass'd
Unproven (490)
Corrections (6)
Classification

talkback
Polls
Forums
Feedback
Bug Reports

downloads
Snapshots
PM Book

information
News
Docs
Wiki
ChangeLog
TODO List
Legalese
About
Owner confidence rating: Very high Entry average rating: No information on entry rating
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$. $ ^*$ 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 $ (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

  • $ \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\}$

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



"Kleene star" is owned by CWoo. [ full author list (2) | owner history (1) ]
(view preamble)

View style:

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

Other names:  asterate
Log in to rate this entry.
(view current ratings)

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

This is version 5 of Kleene star, born on 2002-02-24, modified 2008-05-13.
Object id is 2584, canonical name is KleeneStar.
Accessed 5596 times total.

Classification:
AMS MSC: 68Q70 (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.
[ View all 1 ]
Discussion
Style: Expand: Order:
forum policy

No messages.

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