mathematical logic Mathematical logic is the study of Logic#Formal logic, formal logic within mathematics. Major subareas include model theory, proof theory, set theory, and recursion theory (also known as computability theory). Research in mathematical logic com ...

and

theoretical computer science Theoretical computer science is a subfield of computer science and mathematics that focuses on the Abstraction, abstract and mathematical foundations of computation. It is difficult to circumscribe the theoretical areas precisely. The Associati ...

, the Kleene star (or Kleene operator or Kleene closure) is a unary operation on a

set Set, The Set, SET or SETS may refer to: Science, technology, and mathematics Mathematics *Set (mathematics), a collection of elements *Category of sets, the category whose objects and morphisms are sets and total functions, respectively Electro ...

to generate a set of all finite-length strings that are composed of zero or more repetitions of members from . It was named after American mathematician Stephen Cole Kleene, who first introduced and widely used it to characterize automata for

regular expression A regular expression (shortened as regex or regexp), sometimes referred to as rational expression, is a sequence of characters that specifies a match pattern in text. Usually such patterns are used by string-searching algorithms for "find" ...

s. In mathematics, it is more commonly known as the

free monoid In abstract algebra, the free monoid on a set is the monoid whose elements are all the finite sequences (or strings) of zero or more elements from that set, with string concatenation as the monoid operation and with the unique sequence of zero ...

construction.

Definition

Given a set

V

, define :

V^=\

(the set consists only of the empty string), :

V^=V,

and define recursively the set :

V^=\

for each

i>0.

V^i

is called the

i

-th power of

V

, it is a shorthand for the

concatenation In formal language theory and computer programming, string concatenation is the operation of joining character strings end-to-end. For example, the concatenation of "snow" and "ball" is "snowball". In certain formalizations of concatenati ...

V

by itself

i

times. That is, ''

V^i

'' can be understood to be the set of all strings that can be represented as the concatenation of

i

members from

V

. The definition of Kleene star on

V

is :

V^*=\bigcup_V^i = V^0 \cup V^1 \cup V^2 \cup V^3 \cup V^4 \cup \cdots.

Kleene plus

In some

formal language In logic, mathematics, computer science, and linguistics, a formal language is a set of strings whose symbols are taken from a set called "alphabet". The alphabet of a formal language consists of symbols that concatenate into strings (also c ...

studies, (e.g. AFL theory) a variation on the Kleene star operation called the ''Kleene plus'' is used. The Kleene plus omits the

V^

term in the above union. In other words, the Kleene plus on

V

is :

V^+=\bigcup_ V^i = V^1 \cup V^2 \cup V^3 \cup \cdots,

or :

V^+ = V^*V.

Examples

Example of Kleene star applied to a set of strings: : ^* = . Example of Kleene star applied to a set of strings without the prefix property: : ^* = ;
e.g. the string "aab" can be obtained in several different ways. The Sardinas-Patterson algorithm can be used to check for a given ''V'' whether any member of ''V''^* can be obtained in more than one way. Example of Kleene and Kleene plus applied to a set of characters: : ^* = . : ⁺ = .

Properties

* If

V

is any finite or countably infinite set, then ''

V^*

'' is a countably infinite set. As a result, each

over a finite or countably infinite alphabet

\Sigma

is countable, since it is a subset of the countably infinite set

\Sigma^

. *

(V^)^=V^

, which means that the Kleene star operator is an idempotent unary operator, as

(V^)^=V^

for every

i\geq 1

. *

V^=\

, if

V

is either the

empty set In mathematics, the empty set or void set is the unique Set (mathematics), set having no Element (mathematics), elements; its size or cardinality (count of elements in a set) is 0, zero. Some axiomatic set theories ensure that the empty set exi ...

∅ or the singleton set

\

Generalization

Strings form a

monoid In abstract algebra, a monoid is a set equipped with an associative binary operation and an identity element. For example, the nonnegative integers with addition form a monoid, the identity element being . Monoids are semigroups with identity ...

with concatenation as the binary operation and ε the identity element. In addition to strings, the Kleene star is defined for any monoid. 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''^*. Furthermore, the Kleene star is generalized by including the *-operation (and the union) in the

algebraic structure In mathematics, an algebraic structure or algebraic system consists of a nonempty set ''A'' (called the underlying set, carrier set or domain), a collection of operations on ''A'' (typically binary operations such as addition and multiplicatio ...

itself by the notion of complete star semiring.

Definition

Kleene plus

Examples

Properties

Generalization

See also

Notes

References

Further reading