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

13

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.

mallardz
fonte
3
O seu nome de usuário é o motivo pelo qual você deseja uma boa e velha moda de explicar pato de borracha ?
Babou
@babou Sim. Mas ele falhou hoje :(
mallardz 3/15/15
Sua observação de que o fechamento sob concatenação definido na minha resposta (e na resposta de @David Richerby, explicitamente, como ele nunca menciona explicitamente nenhuma operação de cadeia de caracteres, exceto em um comentário) não incluirá a palavra vazia quite é bastante precisa. Obrigado. Como conseqüência, o operador estrela Kleene não pode representar fechamento sob concatenação: o operador Kleene + representa. No entanto, o operador estrela Kleene pode representar um fechamento sob a operação de energia derivada da concatenação. Eu sou complementada minha resposta para cobrir este aspecto. Foi mais sutil do que o esperado.
babou 5/01/2015
A resposta é legível o suficiente ou devo adicionar uma seção em borracha mais macia?
babou

Respostas:

15

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.nmn+m35

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.SS

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.

David Richerby
fonte
Ok obrigado, sua explicação sobre o fechamento de um conjunto é muito fácil de entender. Mas você quer dizer que Kleene Star é um operador (como mais é um operador) e o fechamento de Kleene é uma operação (como adição)? Também a resposta de Babou de que o nome deriva do fato de que a operação representa essencialmente o fechamento do conjunto sob concatenação faz muito sentido. ?! Embora faz não epsilon baralhar as coisas um pouco lá ...
mallardz
1
@mallardz Bem falando, o encerramento é o cenário; a operação de formação do fechamento é normalmente chamada de "fechamento".
David Richerby
@DavidRicherby: Você poderia chamar o conjunto de números naturais sob subtração como um fechamento ? Você quer dizer que, como o conjunto de expressões regulares fechadas sob o operador kleene * produz uma expressão regular, chamamos de fechamento?
justin
@justin Por definição, o fechamento de qualquer conjunto em uma operação deve ser fechado sob essa operação. Como os naturais não são fechados sob subtração, eles não podem ser o fechamento de nada sob subtração. O conjunto de expressões regulares já está fechado sob a estrela Kleene e o fechamento do conjunto de expressões regulares em alguma operação é, por definição, um conjunto de coisas, não uma única expressão regular. Então, eu realmente não entendo suas perguntas.
David Richerby
@DavidRicherby: Sim, isso é realmente verdade. Por erro, tomei o conjunto de números naturais sob subtração como um número natural inteiro.
justin
7

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 nC } .CnffnCC={f(c1,,cn)c1,,cnC}

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

f(S1,,Sn)={f(s1,,sn)siSi.1in}


C=f(C,,C)

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 ns f } .DfDSDSfSfSSf={f(s1,,sn)s1,,snSf}

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

Sf is the smallest set such that SSf and Sf=f(Sf,,Sf)

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.SSff

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 .ϵSfS+*

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

  1. Extensão a outras propriedades algébricas

    Sff

    SfSfϵ

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

    SDD

    fDSf,1S

    Sf,1={f(s1,s2)s1Sf,1s2D}

    ou com equações definidas:

    Sf,1 is the smallest set such that SSf,1 and Sf,1=f(Sf,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,ϵ) fMϵuM

    uM.u0=ϵ and nNun=f(u,un1)

    unMN0

    MnUn={unuU}unf

    {U0={u0uU}={ϵ}nN,Un=f(U,Un1)
    fM

    U,1UM

    U,1 is the smallest set suchthat UU,1 and U,1=f(U,1,N0)

    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.

fD

  • Df

  • DDf

  • DDff

DfDf

É 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.

babou
fonte
Ei, obrigado, a explicação do fechamento sob concatenação faz muito sentido, mas o epsilon existe no fechamento sob concatenação?
mallardz
ϵ
@DavidRicherby Na verdade, o que eu quis dizer foi se você tem um conjunto S = {m}, então o fechamento sob concatenação de S contém epsilon? Porque m * faz certo? Se não, acho que o fechamento de Kleene não é exatamente equivalente ao fechamento sob concatenação, embora eu ainda possa ver como é aí que o nome se originou. Também me lembro de ler em algum lugar como inicialmente a estrela Kleene era uma operadora binária e evitava produzir epsilon?
mallardz
@DavidRicherby Completei minha resposta na tentativa de atender à objeção justa da @ mallardz.
babou
6

:XXX

  1. xx
  2. xyxy
  3. (x)=x

=(xy)=xy

X=2Σx,yΣxyxy

  1. LL
  2. L1L2L1L2
  3. (L)=L

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

Yuval Filmus
fonte
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.
babou
Respondendo ao meu próprio comentário. A minimalidade é mantida, mas é definida com relação ao conjunto de conjuntos fechados. Nenhuma relação direta com uma operação em cadeias de caracteres, como concatenação. Kleene star e plus são as duas operações de fechamento, mas são definidas usando-se a minoria em relação a diferentes conjuntos de conjuntos fechados. Essa é uma visão muito mais abstrata. (Pelo menos, tenho a satisfação de ver que o raciocínio no nível definido, como finalmente fiz, foi o caminho certo a seguir :). Interessante. Obrigado.
babou