Welcome guest
You're not logged in.
325 users online, thereof 0 logged in

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]

Edit or AddNotationAxiomatic Method

This work was contributed under CC BY-SA 4.0 by:

This work is a derivative of:

Bibliography (further reading)

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

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