13
$\begingroup$

I've found that if I don't understand the etymology behind a cs/programming term, it usually means that I've missed or misunderstood some important underlying concept.

I don't understand why the Kleene star is also called the Kleene closure. Is it related to closures in programming, a function with bound non-local variables?

... on reflection, maybe it is because it allows an open ended set to be written in a closed expression form?

... well in good old rubber-duck-explaining fashion, I'm now guessing that is it, but would still welcome an authoritative answer.

$\endgroup$
  • 3
    $\begingroup$ Is your user name the reason why you want good old rubber-duck-explaining fashion ? $\endgroup$ – babou Jan 3 '15 at 11:30
  • $\begingroup$ @babou Yes. But it failed me today :( $\endgroup$ – mallardz Jan 3 '15 at 16:36
  • $\begingroup$ Your remark that the closure under concatenation defined in my answer (and in @David Richerby's answer, inplicitly as he never mentions explicitly any string operation, except in a comment) will not include the empty word ϵ is quite accurate. Thanks. As a consequence the Kleene star operator cannot be representing closure under concatenation: the Kleene + operator does. However the Kleene star operator may represent closure under the power operation derived from concatenation. I am complemented my answer to cover this aspect. It was more subtle than expected. $\endgroup$ – babou Jan 5 '15 at 5:50
  • $\begingroup$ Is the answer readable enough, or should I add a section in softer rubber? $\endgroup$ – babou Jan 5 '15 at 9:59
15
$\begingroup$

A set is closed under some operator if the result of applying the operator to things in the set is always in the set. For example, the natural numbers are closed under addition because, whenever $n$ and $m$ are natural numbers, $n+m$ is a natural number. On the other hand, the naturals are not closed under subtraction since, for example, $3-5$ is not a natural number.

The closure of a set $S$ under some operator is the smallest set containing $S$ that is closed under the operator. For example, the closure of the natural numbers under subtraction is the integers; the closure of the natural numbers under addition is just the natural numbers, since the set is already closed.

So, "Kleene closure" is not an alternative name for "Kleene star". The Kleene star is the operator; the Kleene closure of a set is the closure of that set under the operator.

$\endgroup$
  • $\begingroup$ Ok thanks, your explanation of a closure of a set is very easy to understand. But do you mean Kleene star is an operator (like plus is an operator) and Kleene closure is an operation (like addition)? Also Babou's answer that the name comes from the fact that the operation essentially represents the closure of the set under concatenation makes a lot of sense. Although doesn't epsilon mess things up slightly there?!... $\endgroup$ – mallardz Jan 3 '15 at 16:50
  • 1
    $\begingroup$ @mallardz Properly speaking, the closure is the set; the operation of forming the closure is normally called "closing". $\endgroup$ – David Richerby Jan 3 '15 at 18:09
  • $\begingroup$ @DavidRicherby:Could you call the set of natural numbers under subtraction as a closure?Do you mean to say that since the set of regular expressions closed under the operator kleene * produces a regular expression we call it a closure? $\endgroup$ – justin Feb 10 '16 at 6:50
  • $\begingroup$ @justin By definition, the closure of any set under an operation must itself be closed under that operation. Since the naturals are not closed under subtraction, they can't be the closure of anything under subtraction. The set of regular expressions is already closed under Kleene star and the closure of the set of regular expressions under some operation is, by definition, a set of things, not a single regular expression. So I don't really understand your questions. $\endgroup$ – David Richerby Feb 10 '16 at 7:53
  • $\begingroup$ @DavidRicherby:Yeah that's really right.By mistake I took the set of natural numbers under subtraction as a whole natural number.Is kleene star related to sets or to finite automata or both? $\endgroup$ – justin Feb 11 '16 at 6:32
7
$\begingroup$

In a nutshell

The name Kleene closure is clearly intended to mean closure under some string operation.

However, careful analysis (thanks to a critical comment by the OP mallardz), shows that the Kleene star cannot be closure under concatenation, which rather corresponds to the Kleene plus operator.

The Kleene star operator actually corresponds to a closure under the power operation derived from concatenation.

The name Kleene star comes from the syntactic representation of the operation with a star *, while closure is what it does.

This is further explained below.
Recall that closure in general, and Kleene star in particular, is an operation on sets, here on sets of strings, i.e. on languages. This will be used in the explanation.

Closure of a subset under an operation always defined

A set $C$ is closed under some $n$-ary operation $f$ iff $f$ is always defined for any $n$-tuple of arguments in $C$ and $C=\{f(c_1,\ldots,c_n)\mid \forall c_1,\ldots,c_n \in C\}$.

By extending $f$ to sets of values in the usual way, i.e. $$f(S_1,\ldots,S_n)=\{f(s_1,\ldots,s_n)\mid \forall s_i\in S_i. 1\leq i\leq n\}$$
we can rewrite the condition as a set equation:
$$C=f(C,\ldots,C)$$

For a domain (or set) $D$ with an operation $f$ that is always defined on $D$, and a set $S\subset D$, The closure of $S$ under $f$ is the smallest set $S_f$ containing $S$ that satisfies the equation: $S_f=\{f(s_1,\ldots,s_n)\mid \forall s_1,\ldots,s_n \in S_f\}$.

More tersely with a set equation, the closure of $S$ under $f$ may be defined by:

$$S_f \text{ is the smallest set such that } S\subset S_f \text{ and } S_f=f(S_f,\ldots,S_f)$$

This is an example of least fixed-point definition, often used in semantics, and also used in formal languages. A context-free grammar can be seen as a system of languages equations (i.e. string set equations), where the non-terminal stand for language variables. The least fixed-point solution associate a language to each variable, and the language thus associated to the intial symbol is the one defined by the CF grammar.

Extending the concept

The closure as defined above is only intended to extend a subset $S$ into a minimal set $S_f$ such that the operation $f$ is always defined.

As remarked by the OP mallardz, this is not a sufficient explanation, since it will not include the empty word $\epsilon$ in $S_f$ when it is not already in $S$. Indeed this closure corresponds to the definition of the Kleene plus + and not to the Kleene star *.

Actually, the idea of closure can be extended, or considered in different ways.

  1. Extension to other algebraic properties

    On way to extend it (though it is no longer called closure) considers more generally an extension to a set $S_f$ having specific algebraic properties with respect to the operation $f$.

    If you define $S_f$ as the smallest set containing $S$ that is a Monoid for the binary function $f$, then you require both closure and a neutral element which is the empty word $\epsilon$.

  2. Extension through a derived operation

    There is a second way which is more properly a closure issue. When you define the closure of $S\subset D$, you can consider it with respect to some of the arguments, while you allow values from the whole set $D$ for the other arguments.

    Considering (for simplicity) a binary function $f$ over $D$, you can define $S_{f,1}$ as the smallest set containing $S$ that satisfies the equation: $$S_{f,1}=\{f(s_1,s_2)\mid \forall s_1\in S_{f,1}\wedge\forall s_2\in D\}$$

    or with set equations:

    $$S_{f,1} \text{ is the smallest set such that } S\subset S_{f,1} \text{ and } S_{f,1}=f(S_{f,1},D)$$

    This also makes sense when the arguments do not belong to the same set. Then you may have closure with respect to some arguments in one set, while considering all possible values for the other arguments (many variations are possible).

    Given a Monoid $(M,f,\epsilon)$ $-$ for example the monoid of strings with concatenation $-$ where $f$ is an associative binary operation on the elements of the set $M$ with an identity element $\epsilon$, you can define the powers of an element $u\in M$ as: $$\forall u\in M.\; u^0=\epsilon\; \text{ and }\; \forall n\in\mathbb N\; u^n=f(u,u^{n-1})$$

    This exponentiation $u^n$ is an operation that takes as argument an element of $M$ and a non-negative integer of $\mathbb N_0$.

    However, the natural extension of this operation to subsets of $M$ is not the usual one which would be, for a given value of $n$, $U^n=\{u^n\mid u\in U\}$. It should rather take into account the original definition of $u^n$ from the operation $f$, wich would give: $$\left\{ \begin{array}{l} U^0=\{u^0\mid u\in U\}=\{\epsilon\}\\ \forall n\in\mathbb N,\; U^n=f(U,U^{n-1}) \end{array} \right.$$ so as to be consistent with the natural extension of the operation $f$ to subsets of $M$.

    Now we can define the closure of $U_{\wedge,1}$ of $U\subset M$ for the first argument of the power operation, as indicated above with the set notation, as: $$U_{\wedge,1} \text{ is the smallest set such that } U\subset U_{\wedge,1} \text{ and } U_{\wedge,1}=f(U_{\wedge,1},\mathbb N_0)$$

    And this does give us the the Kleene star operation when the construction is applied to the concatenation operation of the free Monoid of strings.

    To be completely honest, I am not sure I have not been cheating. But a definition is only what you make it, and that was the only way I found to actually turn the Kleene star into a closure. I may be trying too hard.
    Comments are welcome.

Closing a set under an operation that is not always defined

This is a slightly different view and use of the concept of closure. This view is not really answering the question, but it seems good to keep it in mind to avoid some possible confusions.

The above implies that the function $f$ is always defined in the reference set $D$. That may not always be the case. Then closure can also be a mathematical technique to extend a set so than some operation will always be defined. The way it works in practice is as follow:

  • start with the set $D$ where $f$ is not always defined;

  • build another set $D'$ constructed from elements of $D$, with an operation $f'$ that is always defined, such that you can ...

  • show that there is an isomorphism between $D$ and a subset of $D'$ that is such that $f$ is the image of $f'$ restricted to that subset.

Then the set $D'$ with the operation $f'$ is a closed extension of $D$ with $f$.

That is how integers are built from natural numbers, considering the set of pairs of natural numbers quotiented by an equivalence relation (two pairs are equivalent iff the two elements are in the same order and have the same difference).

This is also how rationals can be built from the integers.

And this is how classical reals can be built from the rationals, though the construction is more complex.

$\endgroup$
  • $\begingroup$ Hey thanks, the closure under concatenation explanation makes a lot of sense, but does epsilon exist in the closure under concatenation? $\endgroup$ – mallardz Jan 3 '15 at 16:55
  • $\begingroup$ @mallardz Yes: $\epsilon$ is the result of concatenation no strings. $\endgroup$ – David Richerby Jan 3 '15 at 21:41
  • $\begingroup$ @DavidRicherby Actually what I meant was if you have a set S = {m} then does the closure under concatenation of S contain epsilon? Because m* does right? If not then I guess Kleene closure is not quite equivalent to closure under concatenation, although I can still see how that is where the name originated. Also I seem to remember reading somewhere how initially Kleene star was a binary operator and avoided producing epsilon? $\endgroup$ – mallardz Jan 4 '15 at 7:52
  • $\begingroup$ @DavidRicherby I completed my answer in an attempt to meet @ mallardz fair objection. $\endgroup$ – babou Jan 4 '15 at 23:51
6
$\begingroup$

Another meaning of closure, which is more general than the meaning explained by David Richerby, is any operator $\ast\colon X \to X$ on a poset $X$ that satisfies the following axioms:

  1. $x \leq x^\ast$
  2. $x \leq y \longrightarrow x^\ast \leq y^\ast$
  3. $(x^\ast)^\ast = x^\ast$

The classical example is topological closure, which also satisfies $\bot^* = \bot$ and $(x \lor y)^* = x^* \lor y^*$, two properties not satisfied by the Kleene star.

The poset in the case of the Kleene star is the poset of all sets of words: $X=2^{\Sigma^*}$. If $x,y \subseteq \Sigma^*$ then $x \leq y$ if $x \subseteq y$. The axioms of closure then state that

  1. $L \subseteq L^\ast$
  2. $L_1 \subseteq L_2 \longrightarrow L_1^* \subseteq L_2^*$
  3. $(L^*)^* = L^*$

The Kleene plus operator also satisfies these axioms, so is also a closure operator under this definition.

$\endgroup$
  • $\begingroup$ Isn't this removing the minimality requirement? I mean, if you remove this requirement, both David Richerby's answer, and my initial answer are OK for the Kleene star. $\endgroup$ – babou Jan 5 '15 at 13:19
  • $\begingroup$ Answering my own comment. Minimality is kept, but is defined with respect to the set of closed sets. No direct relation to an operation on strings such as concatenation. Kleene star and plus are then both closure operations, but defined using minimality with respect to different sets of closed sets. This is a much more abstract view. (At least I have the satisfaction to see that reasonning at the set level as I finally did was the right way to go :). Interesting. Thanks. $\endgroup$ – babou Jan 5 '15 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.