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