Kleene star

Of a language

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

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

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

and define recursively the set

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

where ${\displaystyle wv}$ denotes the string obtained by concatenating ${\displaystyle w}$ and ${\displaystyle v}$. Here, ${\displaystyle L^i}$ can be understood to be the set of all strings that can be obtained by concatenating exactly ${\displaystyle i}$ strings from ${\displaystyle L}$, allowing repetitions.

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

${\displaystyle L^{\ast }=\bigcup _{i\ge 0}{L}^i=L^0\cup L^1\cup L^2\cup L^3\cup L^4\cup \cdots .}$

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

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

or

${\displaystyle V^{+}=V^{\ast }V.}$

Examples

Example of Kleene star applied to a 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 a set of strings without the prefix property:

{"a","ab","b"}^* = { ε, "a", "ab", "b", "aa", "aab", "aba", "abab", "abb", "ba", "bab", "bb", ...};
In this example, the string "aab" can be obtained in two different ways. The Sardinas-Patterson algorithm can be used to check for a given V whether any member of V^* can be obtained in more than one way.

Example of Kleene and Kleene plus applied to a set of characters (following the C programming language convention where a character is denoted by single quotes and a string is denoted by double quotes):

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

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

Properties

• If ${\displaystyle V}$ is any finite or countably infinite set of characters, then ${\displaystyle V^{\ast }}$ is a countably infinite set. As a result, each formal language over a finite or countably infinite alphabet ${\displaystyle \mathrm{\Sigma }}$ is countable, since it is a subset of the countably infinite set ${\displaystyle {\mathrm{\Sigma }}^{\ast }}$.
• ${\displaystyle (L^{\ast }{)}^{\ast }=L^{\ast }}$, which means that the Kleene star operator is an idempotent unary operator, as ${\displaystyle (L^{\ast }{)}^i=L^{\ast }}$ for every ${\displaystyle i\ge 1}$.
• ${\displaystyle V^{\ast }=\{\epsilon \}}$, if ${\displaystyle V}$ is the empty set ∅. For the version of the Kleene star operator on languages, ${\displaystyle L^{\ast }=\{\epsilon \}}$ when ${\displaystyle L}$ is either the empty set ∅ or the singleton set ${\displaystyle \{\epsilon \}}$.

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