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.

Definition: Iteration of Languages, Kleene Star, Kleene Plus 

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]