We have used already the symbol $\Sigma^*$ to denote all words over an alphabet $\Sigma$. The following symbols, proposed by Stephen C. 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$.

Definitions: 1 2 3 4


Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs


References

Bibliography

  1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
  2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015