Kleene star

The Kleene star forms the set of all finite concatenations of zero or more members of a language. Formally, for a language L, L* = ⋃_n≥0 Lⁿ, where L⁰ = {ε} and Lⁿ⁺¹ = LⁿL.¹ Thus, if L = {a}, then L* = {ε, a, aa, aaa, …}; if L = {ab, c}, it includes ε, ab, c, abab, abc, cab, and other finite combinations.

The operation applies to languages as well as regular-expression patterns. The expression (ab|c)* therefore denotes any finite sequence whose individual blocks are either ab or c. “Zero or more” is essential: ε belongs to every Kleene star, even when the repeated expression itself cannot match an empty input.

Kleene star preserves regularity: if L is regular, then L* is regular, and the operation is one of the basic constructors of regular expressions.² It also has useful boundary cases: ∅* = {ε}, while {ε}* = {ε}. These results follow directly from the definition, because a zero-length concatenation is always permitted.

The related Kleene plus, written L⁺, requires one or more repetitions and satisfies L⁺ = LL*; consequently, L* = {ε} ∪ L⁺. Star is not ordinary numerical exponentiation, and it does not mean an infinite repetition. Every word in L* is finite, although L* may contain infinitely many words. The operation is closed under finite concatenation and union in the regular-language framework, but it is not needed to describe every finite language.

In automata theory, a Kleene star is implemented by allowing an automaton to traverse a repeated submachine any finite number of times, including none. A standard construction converts a regular expression into an ε-nondeterministic finite automaton by adding ε-transitions into and around the starred fragment; subset construction can then produce an equivalent deterministic finite automaton.³

Starred patterns appear in lexical analysis, text search, token specifications, and formal descriptions of protocols. In a regular expression, a* matches the empty string and any run of a characters, whereas a+ excludes the empty string. Practical regex engines may add backtracking, capture groups, or nonregular extensions, so the behavior of a programming-language regex is not always identical to the mathematical regular-expression model.⁴

The star operation was named for Stephen Cole Kleene, whose work connected regular expressions with finite automata and helped establish the characterization now called Kleene’s theorem.⁵ In that theorem, the languages recognized by finite automata are exactly the regular languages denoted by regular expressions, with union, concatenation, and star as the central operations.

Star can also be viewed as a least fixed point: L* is the smallest language X containing ε and satisfying X = {ε} ∪ LX. This perspective connects regular expressions with fixed-point methods and dynamic-programming algorithms. A subtle practical edge case arises when a starred subpattern can itself match ε, such as (ε|a)*: the language remains simply a*, but naïve matching procedures may revisit equivalent zero-length states and require safeguards against nontermination or redundant work.

Alphabet

A finite set of symbols from which strings are formed.

Empty string

The string ε with length zero; it is the identity element for concatenation.

Regular language

A language describable by a regular expression or recognizable by a finite automaton.

Kleene plus

The one-or-more repetition operation, written L+ or R+.

ε-transition

An automaton transition that consumes no input symbol.