In
mathematical logic and
computer science, the Kleene star (or Kleene operator or Kleene closure) is a
unary operation, either on
sets of
strings or on sets of symbols or characters. In mathematics,
it is more commonly known as the
free monoid construction. The application of the Kleene star to a set is written as . It is widely used for
regular expressions, which is the context in which it was introduced by
Stephen Kleene to characterize certain
automata, where it means "zero or more repetitions".
If is a set of symbols or characters, then is the set of all strings over symbols in , including the empty string .
The set can also be described as the set containing the empty string and all finite-length strings that can be generated by concatenating arbitrary elements of , allowing the use of the same element multiple times. If is either the
empty set ∅ or the singleton set , then ; if is any other
finite set or
countably infinite set, then is a countably infinite set.[1] As a consequence, each
formal language over a finite or countably infinite alphabet is countable, since it is a subset of the countably infinite set .
(the language consisting only of the empty string),
,
and define recursively the set
for each .
If is a formal language, then , the -th power of the set , is a shorthand for the
concatenation of set with itself times. That is, can be understood to be the set of all
strings that can be represented as the concatenation of strings in .
This means that the Kleene star operator is an
idempotentunary operator: for any set of strings or characters, as for every .
Kleene plus
In some
formal language studies, (e.g.
AFL theory) a variation on the Kleene star operation called the Kleene plus is used. The Kleene plus omits the term in the above union. In other words, the Kleene plus on is
Example of Kleene plus and Kleene star applied to the singleton set containing the empty string:
If , then also for each , hence .
Generalization
Strings form a
monoid with concatenation as the binary operation and ε the identity element. The Kleene star is defined for any monoid, not just strings.
More precisely, let (M, ⋅) be a monoid, and S ⊆ M. Then S* is the smallest submonoid of M containing S; that is, S* contains the neutral element of M, the set S, and is such that if x,y ∈ S*, then x⋅y ∈ S*.
^Fletcher, Peter; Hoyle, Hughes; Patty, C. Wayne (1991). Foundations of Discrete Mathematics. Brooks/Cole. p. 656.
ISBN0534923739. The Kleene closureL* of L is defined to be .
^This equation holds because every element of V+ must either be composed from one element of V and finitely many non-empty terms in V or is just an element of V (where V itself is retrieved by taking V concatenated with ε).