Kleene star

In formal language theory, the Kleene star (or Kleene operator or Kleene closure) refer to two related unary operations, that can be applied either to an alphabet of symbols or to a formal language, a set of strings (finite sequences of symbols).

The Kleene star operator on an alphabet V generates the set V* of all finite-length strings over V, that is, finite sequences whose elements belong to V; in mathematics, it is more commonly known as the free monoid construction. The Kleene star operator on a language L generates another language L*, the set of all strings that can be obtained as a concatenation of zero or more members of L. In both cases, repetitions are allowed.

The Kleene star operators are named after American mathematician Stephen Cole Kleene, who first introduced and widely used it to characterize automata for regular expressions.

Given an alphabet ${\displaystyle V}$, define

and define recursively the set

where ${\displaystyle wv}$ denotes the string obtained by appending the single character ${\displaystyle v}$ to the end of ${\displaystyle w}$. Here, ${\displaystyle V^{i}}$ can be understood to be the set of all strings of length exactly ${\displaystyle i}$, with characters from ${\displaystyle V}$.

The definition of Kleene star on ${\displaystyle V}$ is

Given a language ${\displaystyle L}$ (any finite or infinite set of strings), define