Por que o operador estrela Kleene também é chamado de operador 'fechamento' da Kleene?

Descobri que, se não entendo a etimologia por trás de um termo cs / programação, isso geralmente significa que perdi ou entendi mal algum conceito subjacente importante.

Não entendo por que a estrela Kleene também é chamada de encerramento Kleene. Está relacionado a fechamentos na programação, uma função com variáveis ​​não locais ligadas?

... na reflexão, talvez seja porque permite que um conjunto aberto seja escrito em uma expressão fechada?

... bem, na boa e velha moda explicativa do pato de borracha , agora acho que é isso, mas ainda assim gostaria de receber uma resposta autorizada.

Um conjunto é fechado sob algum operador se o resultado da aplicação do operador a itens do conjunto estiver sempre no conjunto. Por exemplo, os números naturais são fechados em adição porque, sempre que e m são números naturais, n + m é um número natural. Por outro lado, os naturais não são fechados por subtração, pois, por exemplo, 3 - 5 não é um número natural.$n$$m$$n+m$$3-5$

O fechamento de um conjunto sob algum operador é o menor conjunto que contém que é fechado sob o operador. Por exemplo, o fechamento dos números naturais sob subtração é o número inteiro; o fechamento dos números naturais em adição é apenas os números naturais, uma vez que o conjunto já está fechado.$S$$S$

Portanto, "fechamento Kleene" não é um nome alternativo para "estrela Kleene". A estrela Kleene é a operadora; o fechamento Kleene de um conjunto é o fechamento daquele conjunto sob o operador.

Em poucas palavras

O nome de fechamento Kleene pretende claramente significar fechamento sob alguma operação de cadeia.

No entanto, uma análise cuidadosa (graças a um comentário crítico do OP mallardz) mostra que a estrela Kleene não pode ser fechada sob concatenação, o que corresponde ao operador Kleene plus.

O operador estrela Kleene realmente corresponde a um fechamento sob a operação de energia derivada da concatenação.

O nome estrela Kleene vem da representação sintática da operação com uma estrela *, enquanto fechamento é o que ela faz.

Isso é explicado mais abaixo.
Lembre-se de que o fechamento em geral, e a estrela Kleene em particular, é uma operação em conjuntos, aqui em conjuntos de strings, ou seja, em idiomas. Isso será usado na explicação.

Fechamento de um subconjunto em uma operação sempre definida

Um conjunto é fechada sob alguns n operação -ary f sse f é sempre definida para qualquer n -tuple de argumentos em C e C = { f ( c 1 , ... , c n ) | ∀ c 1 , ... , c n ∈ C } .$C$$n$$f$$f$$n$$C$$C=\{f(c_1,\ldots,c_n)\mid \forall c_1,\ldots,c_n \in C\}$

Ao estender para conjuntos de valores da maneira usual, isto é, f ( S 1 , ... , S n ) = { f ( s 1 , ... , s n ) | ∀ s i ∈ S i . 1 ≤ i ≤ n } podemos reescrever a condição como uma equação definida: C = f ( C , … , C $f$

Para um domínio (ou conjunto) com uma operação f que é sempre definida em D e um conjunto S ⊂ D , o fechamento de S sob f é o menor conjunto S f que contém S que satisfaz a equação: S f = { f ( s 1 , ... , s n ) | ∀ s 1 , ... , s n ∈ s f } .$D$$f$$D$$S\subset D$$S$$f$$S_f$$S$$S_f=\{f(s_1,\ldots,s_n)\mid \forall s_1,\ldots,s_n \in S_f\}$

De maneira mais concisa com uma equação definida, o fechamento de sob f pode ser definido por:$S$$f$

Este é um exemplo de definição de ponto menos fixo, geralmente usada em semântica e também em linguagens formais. Uma gramática livre de contexto pode ser vista como um sistema de equações de idiomas (isto é, equações de conjunto de strings), onde os não-terminais representam variáveis ​​de idioma. A solução com menos pontos fixos associa um idioma a cada variável, e o idioma assim associado ao símbolo inicial é aquele definido pela gramática CF.

Ampliando o conceito

Fecho tal como definido acima só foi concebido para estender um subconjunto em um conjunto mínimo S f de tal modo que a operação de f é sempre definida.$S$$S_f$$f$

Como observado pelo mallardz OP, esta não é uma explicação suficiente, uma vez que não irá incluir a palavra vazia em S f quando ele não estiver em S . De fato, esse fechamento corresponde à definição do Kleene plus e não à estrela Kleene .$\epsilon$$S_f$$S$+*

Na verdade, a ideia de fechamento pode ser estendida ou considerada de maneiras diferentes.

1. Extensão a outras propriedades algébricas

   $S_f$$f$

   $S_f$$S$$f$$\epsilon$

2. Extensão através de uma operação derivada

   $S\subset D$$D$

   $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 com equações definidas:

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

   Isso também faz sentido quando os argumentos não pertencem ao mesmo conjunto. Em seguida, você pode encerrar com relação a alguns argumentos em um conjunto, considerando todos os valores possíveis para os outros argumentos (muitas variações são possíveis).

   $(M,f,\epsilon)$ $-$$-$$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})$$

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

   E isso nos dá a operação em estrela Kleene quando a construção é aplicada à operação de concatenação do Monoid livre de strings.

   Para ser completamente honesto, não tenho certeza se não traí. Mas uma definição é apenas o que você faz, e foi a única maneira que encontrei para transformar a estrela Kleene em um fechamento. Eu posso estar tentando demais.
   _{Comentários são bem-vindos.}

Fechar um conjunto em uma operação que nem sempre é definida

Essa é uma visão e uso ligeiramente diferentes do conceito de fechamento. Essa visão não está realmente respondendo à pergunta, mas parece bom manter isso em mente para evitar possíveis confusões.

$f$$D$

• $D$$f$

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

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

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

É assim que números inteiros são construídos a partir de números naturais, considerando o conjunto de pares de números naturais quociente por uma relação de equivalência (dois pares são equivalentes se os dois elementos estiverem na mesma ordem e tiverem a mesma diferença).

É também assim que os racionais podem ser construídos a partir dos números inteiros.

E é assim que os reais clássicos podem ser construídos a partir dos racionais, embora a construção seja mais complexa.

$\ast\colon X \to X$$X$

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

$\bot^* = \bot$$(x \lor y)^* = x^* \lor y^*$

$X=2^{\Sigma^*}$$x,y \subseteq \Sigma^*$$x \leq y$$x \subseteq y$

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

O operador Kleene plus também satisfaz esses axiomas, também é um operador de fechamento sob essa definição.