Kleene star

Given a set ${\displaystyle V}$, define

${\displaystyle V^{0}=\{\varepsilon \}}$ (the language consisting only of the empty string),

${\displaystyle V^{1}=V}$,

and define recursively the set

${\displaystyle V^{i+1}=\{wv:w\in V^{i}{\text{ and }}v\in V\}}$ for each ${\displaystyle i>0}$.

If ${\displaystyle V}$ is a formal language, then ${\displaystyle V^{i}}$, the ${\displaystyle i}$-th power of the set ${\displaystyle V}$, is a shorthand for the concatenation of set ${\displaystyle V}$ with itself ${\displaystyle i}$ times. That is, ${\displaystyle V^{i}}$ can be understood to be the set of all strings that can be represented as the concatenation of ${\displaystyle i}$ strings in ${\displaystyle V}$.

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

${\displaystyle V^{*}=\bigcup _{i\geq 0}V^{i}=V^{0}\cup V^{1}\cup V^{2}\cup V^{3}\cup V^{4}\cup \cdots .}$

This means that the Kleene star operator is an idempotent unary operator: ${\displaystyle (V^{*})^{*}=V^{*}}$ for any set ${\displaystyle V}$ of strings or characters, as ${\displaystyle (V^{*})^{i}=V^{*}}$ for every ${\displaystyle i\geq 1}$.

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 ${\displaystyle V^{0}}$ term in the above union. In other words, the Kleene plus on ${\displaystyle V}$ is

${\displaystyle V^{+}=\bigcup _{i\geq 1}V^{i}=V^{1}\cup V^{2}\cup V^{3}\cup \cdots ,}$

or

${\displaystyle V^{+}=V^{*}V.}$[3]

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 plus applied to set of characters:

{"a", "b", "c"}⁺ = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

Kleene star applied to the same character set:

{"a", "b", "c"}^* = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", "aab", ...}.

Example of Kleene star applied to the empty set:

∅^* = {ε}.

Example of Kleene plus applied to the empty set:

∅⁺ = ∅ ∅^* = { } = ∅,

where concatenation is an associative and noncommutative product.

Example of Kleene plus and Kleene star applied to the singleton set containing the empty string:

If ${\displaystyle V=\{\varepsilon \}}$, then also ${\displaystyle V^{i}=\{\varepsilon \}}$ for each ${\displaystyle i}$, hence ${\displaystyle V^{*}=V^{+}=\{\varepsilon \}}$.

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, ⋅) be a monoid, and S ⊆ 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 ∈ S^*, then x⋅y ∈ S^*.

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.[4]

• Wildcard character
• Glob (programming)

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