Kleene star
Encyclopedia
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. The application of the Kleene star to a set V is written as V*. It is widely used for regular expression
s, which is the context in which it was introduced by Stephen Kleene to characterise certain automata
, where it means "zero or more".
That is, V* is the collection of all possible finite-length strings generated from the strings in V.
The operators are used in rewrite rule
s for generative grammar
s.
define recursively the set
where 
If V is a formal language, then Vi, the i-th power of the set V, is a shorthand for the concatenation
of set V with itself i times. That is, Vi can be understood to be the set of all strings
that can be represented as the concatenation of i strings in
.
The definition of Kleene star on V is
Additionally, the Kleene Star is used in Optimality Theory
.
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 star applied to set of characters:
Example of Kleene star applied to the empty set:
Example of Kleene plus applied to the empty set:
Note that for every set L,
equals the concatenation of L with 
.
In contrast,
can be written as 
.
The operators
and 
describe the same set if and only if the set L under
consideration contains the empty word.
with concatenation as the binary operation and λ the identity element. The Kleene star is defined for any monoid, not just strings.
More precisely, let
be a monoid, and 
. Then 
is the smallest submonoid of 
containing 
; that is, 
contains the neutral element of 
, the set 
, and is such that if 
, then 
.
Mathematical logic
Mathematical logic is a subfield of mathematics with close connections to foundations of mathematics, theoretical computer science and philosophical logic. The field includes both the mathematical study of logic and the applications of formal logic to other areas of mathematics...
and computer science
Computer science
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, the Kleene star (or Kleene operator or Kleene closure) is a unary operation
Unary operation
In mathematics, a unary operation is an operation with only one operand, i.e. a single input. Specifically, it is a functionf:\ A\to Awhere A is a set. In this case f is called a unary operation on A....
, either on sets of strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
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 expression
Regular expression
In computing, a regular expression provides a concise and flexible means for "matching" strings of text, such as particular characters, words, or patterns of characters. Abbreviations for "regular expression" include "regex" and "regexp"...
s, which is the context in which it was introduced by Stephen Kleene to characterise certain automata
Automata theory
In theoretical computer science, automata theory is the study of abstract machines and the computational problems that can be solved using these machines. These abstract machines are called automata...
, where it means "zero or more".
- If V is a set of strings then V* is defined as the smallest supersetSuperSetSuperSet Software was a group founded by friends and former Eyring Research Institute co-workers Drew Major, Dale Neibaur, Kyle Powell and later joined by Mark Hurst...
of V that contains λ (the empty string) and is closedClosure (mathematics)In mathematics, a set is said to be closed under some operation if performance of that operation on members of the set always produces a unique member of the same set. For example, the real numbers are closed under subtraction, but the natural numbers are not: 3 and 8 are both natural numbers, but...
under the string concatenation operationConcatenationIn computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
. This set can also be described as the set of strings that can be made by concatenating zero or more strings from V. - If V is a set of symbols or characters then V* is the set of all strings over symbols in V, including the empty stringEmpty stringIn computer science and formal language theory, the empty string is the unique string of length zero. It is denoted with λ or sometimes Λ or ε....
.
That is, V* is the collection of all possible finite-length strings generated from the strings in V.
The operators are used in rewrite rule
Rewrite rule
In linguistics, a rewrite rule for natural language in generative grammar is a rule of the form A → X where A is a syntactic category label, such as noun phrase or sentence, and X is a sequence of such labels and/or morphemes, expressing the fact that A can be replaced by X in generating the...
s for generative grammar
Generative grammar
In theoretical linguistics, generative grammar refers to a particular approach to the study of syntax. A generative grammar of a language attempts to give a set of rules that will correctly predict which combinations of words will form grammatical sentences...
s.
Definition and notation
Givendefine recursively the set
where If V is a formal language, then Vi, the i-th power of the set V, is a shorthand for the concatenation
Concatenation
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
of set V with itself i times. That is, Vi can be understood to be the set of all strings
String (computer science)
In formal languages, which are used in mathematical logic and theoretical computer science, a string is a finite sequence of symbols that are chosen from a set or alphabet....
that can be represented as the concatenation of i strings in
.The definition of Kleene star on V is
Additionally, the Kleene Star is used in Optimality Theory
Optimality theory
Optimality theory is a linguistic model proposing that the observed forms of language arise from the interaction between conflicting constraints. OT models grammars as systems that provide mappings from inputs to outputs; typically, the inputs are conceived of as underlying representations, and...
.
Kleene plus
In some formal languageFormal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
studies, (e.g. AFL Theory
Abstract family of languages
In computer science, in particular in the field of formal language theory,the term abstract family of languages refers to an abstract mathematical notion generalizing characteristics common to the regular languages, the context-free languages and the recursively enumerable languages, and other...
) 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 isExamples
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", "ca", "cb", "cc", ...}.
Example of Kleene star applied to the empty set:
Example of Kleene plus applied to the empty set:
Note that for every set L,
equals the concatenation of L with .In contrast,
can be written as .The operators
and describe the same set if and only if the set L underconsideration contains the empty word.
Generalization
Strings form a monoidMonoid
In abstract algebra, a branch of mathematics, a monoid is an algebraic structure with a single associative binary operation and an identity element. Monoids are studied in semigroup theory as they are naturally semigroups with identity. Monoids occur in several branches of mathematics; for...
with concatenation as the binary operation and λ the identity element. The Kleene star is defined for any monoid, not just strings.
More precisely, let
be a monoid, and . Then is the smallest submonoid of containing ; that is, contains the neutral element of , the set , and is such that if , then .See also
- A* search algorithm
- Kleene algebraKleene algebraIn mathematics, a Kleene algebra is either of two different things:* A bounded distributive lattice with an involution satisfying De Morgan's laws , additionally satisfying the inequality x∧−x ≤ y∨−y. Kleene algebras are subclasses of Ockham algebras...
- Extended Backus-Naur form
- Pumping lemmaPumping lemmaIn the theory of formal languages in computability theory, a pumping lemma or pumping argument states that, for a particular language to be a member of a language class, any sufficiently long string in the language contains a section, or sections, that can be removed, or repeated any number of...
- Star heightStar heightIn theoretical computer science, more precisely in the theory of formal languages, the star height is a measure for the structural complexityof regular expressions: The star height equals the maximum nesting depth of stars appearing in the regular expression....
- Optimality TheoryOptimality theoryOptimality theory is a linguistic model proposing that the observed forms of language arise from the interaction between conflicting constraints. OT models grammars as systems that provide mappings from inputs to outputs; typically, the inputs are conceived of as underlying representations, and...
- Formal grammarFormal grammarA formal grammar is a set of formation rules for strings in a formal language. The rules describe how to form strings from the language's alphabet that are valid according to the language's syntax...
- Finite automata
- Arden's RuleArden's RuleIn theoretical computer science, Arden's rule, also known as Arden's lemma, is a mathematical statement abouta certain form of language equations.-Background:...