In formal language theory, the Kleene star (or Kleene operator or Kleene closure) refers 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 generates the set of all finite-length strings over ,
:<math> L^*=\bigcup_{i \ge 0 }L^i = L^0 \cup L^1 \cup L^2 \cup L^3 \cup L^4 \cup \cdots.</math>
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 <math>V^{0}</math> or <math>L^0</math> term in the above unions. In other words, the Kleene plus on <math>V</math> is
:<math>V^+=\bigcup_{i \geq 1} V^i = V^1 \cup V^2 \cup V^3 \cup \cdots,</math>
or
:<math>V^+ = V^*V.</math> As a result, each formal language over a finite or countably infinite alphabet <math>\Sigma</math> is countable, since it is a subset of the countably infinite set <math>\Sigma^{*}</math>.
- <math>(L^{*})^{*}=L^{*}</math>, which means that the Kleene star operator is an idempotent unary operator, as <math>(L^{*})^{i}=L^{*}</math> for every <math>i\geq 1</math>.
- <math>V^{*}=\{\varepsilon\}</math>, if <math>V</math> is the empty set ∅. For the version of the Kleene star operator on languages, <math>L^{*}=\{\varepsilon\}</math> when <math>L</math> is either the empty set ∅ or the singleton set <math>\{\varepsilon\}</math>.
Generalization
Strings form a monoid 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<sup>*</sup> is the smallest submonoid of M containing S; that is, S<sup>*</sup> contains the neutral element of M, the set S, and is such that if x,y ∈ S<sup>*</sup>, then x⋅y ∈ S<sup>*</sup>.
Furthermore, the Kleene star is generalized by including the *-operation (and the union) in the algebraic structure itself by the notion of complete star semiring.
See also
- Wildcard character
- Glob (programming)