Pourquoi l'opérateur étoile de Kleene est-il également appelé opérateur de «fermeture» de Kleene?

J'ai trouvé que si je ne comprends pas l'étymologie derrière un terme cs / programmation, cela signifie généralement que j'ai manqué ou mal compris un concept sous-jacent important.

Je ne comprends pas pourquoi l'étoile Kleene est aussi appelée la fermeture Kleene. Est-ce lié aux fermetures de programmation, une fonction avec des variables non locales liées?

... à la réflexion, c'est peut-être parce qu'il permet d'écrire un ensemble ouvert sous une forme d'expression fermée?

... bien dans la bonne vieille façon d' expliquer le canard en caoutchouc , je suppose maintenant que c'est ça, mais j'aimerais toujours une réponse faisant autorité.

Un ensemble est fermé sous un opérateur si le résultat de l'application de l'opérateur à des éléments de l'ensemble est toujours dans l'ensemble. Par exemple, les nombres naturels sont fermés sous addition car, chaque fois que et m sont des nombres naturels, n + m est un nombre naturel. D'un autre côté, les naturels ne sont pas fermés par soustraction puisque, par exemple, 3 - 5 n'est pas un nombre naturel.$n$$m$$n+m$$3-5$

La fermeture d'un ensemble sous un opérateur est le plus petit ensemble contenant S qui est fermé sous l'opérateur. Par exemple, la fermeture des nombres naturels soustraits est les entiers; la fermeture des nombres naturels sous addition n'est que les nombres naturels, puisque l'ensemble est déjà fermé.$S$$S$

Ainsi, "fermeture Kleene" n'est pas un nom alternatif pour "étoile Kleene". L'étoile Kleene est l'opérateur; la fermeture Kleene d'un ensemble est la fermeture de cet ensemble sous l'opérateur.

En un mot

Le nom de fermeture Kleene est clairement destiné à signifier la fermeture sous une opération de chaîne.

Cependant, une analyse minutieuse (grâce à un commentaire critique de l'OP mallardz), montre que l'étoile Kleene ne peut pas être fermée sous concaténation, ce qui correspond plutôt à l'opérateur Kleene plus.

L'opérateur étoile de Kleene correspond en fait à une fermeture sous l'opération de puissance dérivée de la concaténation.

Le nom étoile Kleene vient de la représentation syntaxique de l'opération avec une étoile *, tandis que la fermeture est ce qu'elle fait.

Ceci est expliqué plus en détail ci-dessous.
Rappelons que la fermeture en général, et l'étoile de Kleene en particulier, est une opération sur les ensembles, ici sur les ensembles de chaînes, c'est-à-dire sur les langues. Cela sera utilisé dans l'explication.

Clôture d'un sous-ensemble sous une opération toujours définie

Un ensemble est fermé sous une opération n -aire f ssi f est toujours défini pour tout$C$$n$$f$$f$ -tuple d'arguments dans C et C = { f ( c 1 , … , c n ) ∣ ∀ c 1 , … , c n ∈ C } .$n$$C$$C=\{f(c_1,\ldots,c_n)\mid \forall c_1,\ldots,c_n \in C\}$

En étendant à des ensembles de valeurs de la manière habituelle, c'est-à-dire f ( S 1 , … , S n ) = { f ( s 1$f$ on peut réécrire la condition comme une équation d'ensemble: C = f ( C , … , C

Pour un domaine (ou ensemble) avec une opération f toujours définie sur D , et un ensemble S ⊂ D , la fermeture de S sous f est le plus petit ensemble S f contenant $D$$f$$D$$S\subset D$$S$$f$$S_f$$S$ qui satisfait l'équation: .$S_f=\{f(s_1,\ldots,s_n)\mid \forall s_1,\ldots,s_n \in S_f\}$

Plus précisément avec une équation établie, la fermeture de sous f peut être définie par:$S$$f$

Il s'agit d'un exemple de définition du point le moins fixe, souvent utilisé en sémantique, et également utilisé dans les langages formels. Une grammaire sans contexte peut être considérée comme un système d'équations de langues (c'est-à-dire des équations de chaînes de caractères), où le non-terminal représente des variables de langue. La solution la moins fixe associe un langage à chaque variable, et le langage ainsi associé au symbole initial est celui défini par la grammaire CF.

Élargir le concept

La fermeture telle que définie ci-dessus est uniquement destinée à étendre un sous-ensemble dans un ensemble minimal S f de sorte que l'opération f est toujours définie.$S$$S_f$$f$

Comme le fait remarquer le mallardz OP, ce n'est pas une explication suffisante, car elle ne comprend pas le mot vide dans S f quand il est pas déjà dans S . En effet cette fermeture correspond à la définition de la Kleene plus et non à l'étoile Kleene .$\epsilon$$S_f$$S$+*

En fait, l'idée de fermeture peut être étendue ou envisagée de différentes manières.

1. Extension à d'autres propriétés algébriques

   En voie de l'étendre (bien qu'elle ne soit plus appelée fermeture ) envisage plus généralement une extension à un ensemble ayant des propriétés algébriques spécifiques par rapport à l'opération f .$S_f$$f$

   Si vous définissez comme le plus petit ensemble contenant S qui est un monoïde pour la fonction binaire f , alors vous avez besoin à la fois de fermeture et d'un élément neutre qui est le mot vide ϵ .$S_f$$S$$f$$\epsilon$

2. Extension via une opération dérivée

   Il y a une deuxième voie qui est plus proprement une question de fermeture. Lorsque vous définissez la fermeture de , vous pouvez la considérer par rapport à certains des arguments, tandis que vous autorisez les valeurs de l'ensemble D pour les autres arguments.$S\subset D$$D$

   En considérant (pour simplifier) ​​une fonction binaire sur D , vous pouvez définir S f , 1 comme le plus petit ensemble contenant S qui satisfait l'équation: S f , 1 = { f ( s $f$$D$$S_{f,1}$$S$

   $$S_{f,1}=\{f(s_1,s_2)\mid \forall s_1\in S_{f,1}\wedge\forall s_2\in D\}$$

   ou avec des équations définies:

   $$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)$$

   Cela a également un sens lorsque les arguments n'appartiennent pas au même ensemble. Ensuite, vous pouvez avoir la fermeture par rapport à certains arguments dans un ensemble, tout en considérant toutes les valeurs possibles pour les autres arguments (de nombreuses variantes sont possibles).

   Étant donné un monoïde - par exemple le monoïde de chaînes avec concaténation $(M,f,\epsilon)$ $-$$-$ où est une opération binaire associative sur les éléments de l'ensemble M avec un élément d'identité ϵ , vous pouvez définir les puissances d'un élément u ∈ M en tant que: ∀ u ∈ M $f$$M$$\epsilon$$u\in M$

   $$\forall u\in M.\; u^0=\epsilon\; \text{ and }\; \forall n\in\mathbb N\; u^n=f(u,u^{n-1})$$

   Cette exponentiation est une opération qui prend comme argument un élément de M et un entier non négatif de N 0 .$u^n$$M$$\mathbb N_0$

   $M$$n$$U^n=\{u^n\mid u\in U\}$$u^n$$f$

   $$\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.$$ $f$$M$

   $U_{\wedge,1}$$U\subset M$

   $$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)$$

   Et cela nous donne l'opération étoile de Kleene lorsque la construction est appliquée à l'opération de concaténation du monoïde libre de cordes.

   Pour être tout à fait honnête, je ne suis pas sûr de ne pas avoir triché. Mais une définition n'est que ce que vous en faites, et c'est la seule façon que j'ai trouvée de transformer réellement l'étoile Kleene en fermeture. Je fais peut-être trop d'efforts.
   _{Les commentaires sont les bienvenus.}

Fermer un ensemble sous une opération qui n'est pas toujours définie

Il s'agit d'une vision et d'une utilisation légèrement différentes du concept de fermeture. Ce point de vue ne répond pas vraiment à la question, mais il semble bon de le garder à l'esprit pour éviter certaines confusions possibles.

$f$$D$

• $D$$f$

• $D'$$D$$f'$

• $D$$D'$$f$$f'$

$D'$$f'$$D$$f$

C'est ainsi que les entiers sont construits à partir de nombres naturels, en considérant l'ensemble des paires de nombres naturels quotientées par une relation d'équivalence (deux paires sont équivalentes si les deux éléments sont dans le même ordre et ont la même différence).

C'est aussi ainsi que les rationnels peuvent être construits à partir des entiers.

Et c'est ainsi que les réels classiques peuvent être construits à partir des rationnels, bien que la construction soit plus complexe.

Un autre sens de la fermeture, which is more general than the meaning explained by David Richerby, is any operator $\ast\colon X \to X$ sur un 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^*$, deux propriétés non satisfaites par l'étoile Kleene.

Le poset dans le cas de l'étoile de Kleene est le poset de tous les ensembles de mots: $X=2^{\Sigma^*}$. Si$x,y \subseteq \Sigma^*$ ensuite $x \leq y$ si $x \subseteq y$. Les axiomes de fermeture indiquent alors que

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

L'opérateur Kleene plus satisfait également ces axiomes, il en va de même pour l'opérateur de fermeture selon cette définition.