Kleene star

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 expressions, which is the context in which it was introduced by Stephen Kleene to characterise certain automata, where it means "zero or more".

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.
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.

The set V* can also be described as the set of finite-length strings that can be generated by concatenating arbitrary elements of V allowing the use of the same element multiple times. If V is a nonempty finite set then V* is a countably infinite set .

The operators are used in rewrite rules for generative grammars.

Definition and notation

Given

$V_0=\{\lambda\}\,$

define recursively the set

$V_{i+1}=\{wv \mid w\in V_i \mbox{ and } v \in V\}\,$ where $i \ge 0\,.$

If V is a formal language, then V_i, the i-th power of the set V, is a shorthand for the concatenation of set V with 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 strings in V.

The definition of Kleene star on V is

$V^*=\bigcup_{i \in \N}V_i = \left \{\lambda \right\} \cup V_1 \cup V_2 \cup V_3 \cup \ldots.$

Additionally, the Kleene Star is used in Optimality Theory.

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 V₀ term in the above union. In other words, the Kleene plus on V is $V^+=\bigcup_{i \in \N \setminus \{0\}}\!\!\!\! V_i = V_1 \cup V_2 \cup V_3 \cup \ldots.$

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", "ca", "cb", "cc", ...}.

Example of Kleene star applied to the empty set:

$\varnothing ^* =\{\lambda\}.$

Example of Kleene plus applied to the empty set:

$\varnothing ^+ = \varnothing \varnothing ^* =\{\}= \varnothing,$

where concatenation is written as an associative and noncommutative product, sharing these properties with the Cartesian product of sets.

Note that for every set L, L ⁺ equals the concatenation of L with L ^* . In contrast, L ^* can be written as $\{\lambda\} \cup L^+$. The operators L ⁺ and L ^* describe the same set if and only if the set L under consideration contains the empty word.

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, \cdot)$ be a monoid, and $S \subseteq 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 \in S^*$, then $x \cdot y \in S^*$.

See also

• A* search algorithm
• Kleene algebra
• Extended Backus-Naur form
• Pumping lemma
• Star height
• Optimality Theory
• Formal grammar
• Finite automata
• Arden's Rule

References

The definition of Kleene star is found in virtually every textbook on automata theory. A standard reference is the following:

• Hopcroft, John E.; Ullman, Jeffrey D. (1979). Introduction to Automata Theory, Languages, and Computation (1st ed.). Addison-Wesley.