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 In mathematics, a unary operation is an operation with only one operand, i.e. a single input. This is in contrast to ''binary operations'', which use two operands. An example is any function , where is a set; the function 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 Stephen Cole Kleene ( ; January 5, 1909 – January 25, 1994) was an American mathematician. One of the students of Alonzo Church, Kleene, along with Rózsa Péter, Alan Turing, Emil Post, and others, is best known as a founder of the branch of ...

, who first introduced and widely used it to characterize

automata An automaton (; : automata or automatons) is a relatively self-operating machine, or control mechanism designed to automatically follow a sequence of operations, or respond to predetermined instructions. Some automata, such as bellstrikers i ...

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 Idempotence (, ) is the property of certain operations in mathematics and computer science whereby they can be applied multiple times without changing the result beyond the initial application. The concept of idempotence arises in a number of pl ...

unary operator In mathematics, a unary operation is an operation with only one operand, i.e. a single input. This is in contrast to ''binary operations'', which use two operands. An example is any function , where is a set; the function is a unary operatio ...

, 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 In abstract algebra, a semiring is an algebraic structure. Semirings are a generalization of rings, dropping the requirement that each element must have an additive inverse. At the same time, semirings are a generalization of bounded distributi ...

Definition

Kleene plus

Examples

Properties

Generalization

See also

Notes

References

Further reading