1.3.2. The Kleene Star (Kleene closure)

The Kleene Star (named after Stephen Cole Kleene) is a mathematical operator used in formal language theory and theoretical computer science. It applies to sets of strings and describes arbitrary repetitions (including no repetition) of those strings.

Note

In set theory, If \(\Sigma\) is a set equipped with one or several methods for producing elements from other elements of \(\Phi\). A subset \(\Phi\) of \(\Sigma\) is said to be closed under these methods when all input are in \(\Phi\) and all possible result elements are also in \(\Phi\).

As you will see from this definition the Kleene star is also a closure.

1.3.2.1. Formal Definition

Given \(\Sigma\) be an alphabet, and \(L \subseteq \Sigma^*\) be a language (a set of strings formed from \(\Sigma\)). The Kleene star of \(L\), denoted \(L^*\), is defined as follows:

\[L^* = \bigcup_{n=0}^{\infty} L^n\]

Where :

  • \(L^0 = \{\varepsilon\}\), the empty string

  • \(L^n,\ n \geq 1\) is the set of strings formed by concatenated \(n\) elements of \(A\)

1.3.2.2. Kleene closure

The kleene star is a closure because it includes all strings formed by repeated concatenation of words from a given language, as well a the empty string.

  • \(L^0 = \{\varepsilon\}\) the empty string

  • \(L^1 = L\) the set of words from \(L\)

  • \(L^2\) is the set all strings of length 2 by concatenating to words from \(L\)

  • and so on for the powers \(L^n, n \geq 0\)

1.3.2.3. Example

1.3.2.3.1. Classical example

The Kleene star is a fundamental construct used to describe regular language in regular expressions.

  1. By definition, the Kleene star always includes the empty string \(\varepsilon\), even if \(A\)

  2. If \(A = \{a,\ b\}\), then \(A^* = \{\varepsilon,\ a,\ b,\ aa,\ ab,\ ba,\ bb,\ aaa,\ aab,\ aba,...\}\)

1.3.2.3.2. Binary alphabet

Let us consider the binary alphabet \(\Sigma = \{0,\ 1\}\)

The Kleene star of this alphabet, denoted \(\Sigma^*\), is the set of all possible strings of 0 and 1, including the empty string :

\[\Sigma^* = \{\varepsilon,\ 0,\ 1,\ 00,\ 01,\ 10,\ 11,\ 000,\ 001,\ 010,\ 011,\ 100,\ 101,\ 111,\ ...\}\]

1.3.2.4. Differences with \(+\) operator

The Kleene plus operator (\(A⁺\)) is similar sur the kleene star, but it excludes the possibility of no repetitions.

\[\begin{split}A⁺ = A^* \setminus \{\varepsilon\} = \bigcup_{n=1}^{\infty} A_n \\ or \\ A^* = A⁺ \cup \{\varepsilon\}\end{split}\]