In mathematical logic and computer science, the Kleene star (or Kleene closure) is a unary operation, either on sets of strings or on sets of symbols or characters. The application of the Kleene star to a set V is written as V*. It is widely used for regular expressions, which is the context in which it was introduced by Stephen Kleene to characterise certain automata. To meet Wikipedias quality standards, this article or section may require cleanup. ... Computer science, or computing science, is the study of the theoretical foundations of information and computation and their implementation and application in computer systems. ... In mathematics, a unary operation is an operation with only one operand. ... In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ... In computer programming and some branches of mathematics, strings are sequences of various simple objects. ... In computing, a regular expression (abbreviated as regexp or regex, with plural forms regexps, regexes, or regexen) is a string that describes or matches a set of strings, according to certain syntax rules. ... Stephen Cole Kleene (January 5, 1909 - January 25, 1994) was an American mathematician whose work at the University of Wisconsin-Madison helped lay the foundations for theoretical computer science. ... An automaton (plural: automata) is a self-operating machine. ...

1. If V is a set of strings then V* is defined as the smallest superset of V that contains ε (the empty string) and is closed under the string concatenation operation. This set can also be described as the set of strings that can be made by concatenating zero or more strings from V.
2. If V is a set of symbols or characters then V* is the set of all strings over symbols in V, including the empty string.

A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ... In mathematics, the closure C(X) of an object X is defined to be the smallest object that both includes X as a subset and possesses some given property. ... Concatenation is a standard operation in computer programming languages (a subset of formal language theory). ... In various branches of mathematics and computer science, strings are sequences of various simple objects (symbols, tokens, characters, etc. ...

Set-theoretic definition and notation

• The k-th power of a set V is shorthand for the Cartesian product of V, k − 1 times - e.g. .

• 1 denotes the identity event , the set containing only the empty string.
• 0 denotes the empty event .

Examples

Example of Kleene star applied to set of strings:

{"ab", "c"}* = {ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}

Example of Kleene star applied to set of characters:

{'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", ...}

Generalization

The Kleene star is often generalized for any monoid (M, ), that is, a set M and binary operation on M such that In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single, associative binary operation and an identity element. ...

• (closure)
• (associativity)
• (identity)

If V is a subset of M, then V* is defined as the smallest superset of V that contains ε (the empty string) and is closed under the operation. V* is then itself a monoid, and is called the monoid generated by V. This is a generalization of the Kleene star discussed above since the set of all strings over some set of symbols forms a monoid (with string concatenation as binary operation). In mathematics, the closure C(X) of an object X is defined to be the smallest object that both includes X as a subset and possesses some given property. ... In mathematics, associativity is a property that a binary operation can have. ... In mathematics, an identity element (or neutral element) is a special type of element of a set with respect to a binary operation on that set. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, the terms, subset, superset and proper (or strict) subset or superset are used to describe the relation, called inclusion, of one set being contained inside another set. ... A is a subset of B, and B is a superset of A. In mathematics, especially in set theory, a set A is a subset of a set B, if A is contained inside B. The relationship of one set being a subset of another is called inclusion. ...

See also

• Kleene algebra
• Extended Backus-Naur form
• Pumping Lemma
• Star height problem, generalized star height problem, star-free language
• Regular expressions