Kleene Star, ‘∗’

Kleene Star, ‘∗’

Star performs the union of repeated exponentiations:

L∗ = {x | ∃k ∈ N : x ∈ Lk}.

This definition can also be written as

L∗ = ∪k≥0 Lk,

or even as

L∗ = ∪k∈Nat Lk.

Notice that according to these definitions, ∅∗ = {ε} This is because for any k, ∅k is defined to be {ε}. In turn, this is so because we must have a basis element in the recursive definition of concatenation. In our case, ε is the identity for string concatenation.

Examples:

• {a, b, c}∗ is all possible strings over a, b, and c, including the empty string ε.

• {a, bc}∗ is all possible strings formed by concatenating a and bc in some order some number of times. In other words, all the strings in

{a, bc}k, for all k, are present in this set.

In a programming sense, star is iteration that is unable to keep track of the iteration count. The ability to “forget” the number of iterations is crucial to obtaining simpler languages, and ultimately, decidability.

Complementation: Using the above-defined notion of star, we can now specify a universe Σ∗ of strings, and define complementation with respect to that universe:

L = {x | x ∈ Σ∗ \ L}.

Reversal: The notion of reversing a string is pretty straightforward - we simply put the first character last, the second character penultimate, and so on. The definition of reverse(s) for s being a string in some alphabet, is as follows:

reverse(ε) = ε

reverse(s as ax) = reverse(x) ◦ a.

We use the as construct to elaborate a quantity. ‘s as ax’ means ‘view string s as a concatenation of symbol a and string x.’ The term ‘reverse(x) ◦ a’ says ‘reverse x and append a to its end.’

For language L, reverse(L) is then {reverse(x) | x ∈ L}.