We have used already the symbol $\Sigma^*$ to denote all words over an alphabet $\Sigma$. The following symbols, proposed by Stephen Cole Kleene (1909 – 1994) prove very useful in theoretical computer science and are generalizations of this concept for any languages.

Let $L$ be a languages over an alphabets with the empty word $\epsilon$. The **iteration** $L^n$ of $L$ is a repeated concatenation of itself, defined recursively by $$L^0:=\{\epsilon\}\quad L^{n+1}:=LL^n.$$

The **Kleene star** $L^*$ is the union $$L^*:=\bigcup_{i\ge 0}L^i$$ of all of its iterations (i.e. including the empty word). In comparison, the **Kleene plus** $L^+$ excludes the empty word: $$L^+:=L^*\setminus\{\epsilon\}=\bigcup_{i\ge 1}L^i.$$

The symbols $L^*$ and $L^+$ are sometimes also called **Kleene closures** of $L$.

| | | | | created: 2020-05-04 20:13:49 | modified: 2020-05-06 13:02:06 | by: *bookofproofs* | references: [1086], [7895]

[1086] **Erk, Katrin; Priese, Lutz**: “Theoretische Informatik”, Springer Verlag, 2000, 2. Auflage

[7895] **Hoffmann, Dirk**: “Theoretische Informatik, 3. Auflage”, Hanser, 2015