¿Por qué el operador estrella de Kleene también se llama operador de "cierre" de Kleene?

13

Descubrí que si no entiendo la etimología detrás de un término cs / programación, generalmente significa que he perdido o malinterpretado algún concepto subyacente importante.

No entiendo por qué la estrella de Kleene también se llama cierre de Kleene. ¿Está relacionado con los cierres en la programación, una función con variables no locales vinculadas?

... en reflexión, ¿tal vez es porque permite que un conjunto abierto se escriba en una forma de expresión cerrada?

... bueno, en la buena y antigua manera de explicar el pato de goma , ahora supongo que es eso, pero aún así agradecería una respuesta autorizada.

mallardz
fuente
3
¿Es su nombre de usuario la razón por la que quiere una buena moda antigua que explique el pato de goma ?
babou
@babou Sí. Pero hoy me falló :(
mallardz
Su observación de que el cierre bajo concatenación definido en mi respuesta (y en la respuesta de @David Richerby, de manera implícita ya que nunca menciona explícitamente ninguna operación de cadena, excepto en un comentario) no incluirá la palabra vacía ϵ es bastante precisa. Gracias. Como consecuencia, el operador estrella de Kleene no puede representar el cierre bajo concatenación: el operador Kleene + sí. Sin embargo, el operador estrella de Kleene puede representar el cierre bajo la operación de energía derivada de la concatenación. Complemento mi respuesta para cubrir este aspecto. Fue más sutil de lo esperado.
babou
¿La respuesta es lo suficientemente legible o debo agregar una sección en goma más suave?
babou

Respuestas:

15

Un conjunto se cierra bajo algún operador si el resultado de aplicar el operador a elementos del conjunto siempre está en el conjunto. Por ejemplo, los números naturales se cierran mediante la suma porque, siempre que y m son números naturales, n + m es un número natural. Por otro lado, los naturales no se cierran bajo sustracción ya que, por ejemplo, 3 - 5 no es un número natural.nmn+m35

El cierre de un conjunto debajo de algún operador es el conjunto más pequeño que contiene S que está cerrado debajo del operador. Por ejemplo, el cierre de los números naturales bajo resta son los enteros; el cierre de los números naturales que se suman son solo los números naturales, ya que el conjunto ya está cerrado.SS

Entonces, "cierre de Kleene" no es un nombre alternativo para "estrella de Kleene". La estrella de Kleene es el operador; El cierre de Kleene de un conjunto es el cierre de ese conjunto bajo el operador.

David Richerby
fuente
Ok, gracias, tu explicación del cierre de un conjunto es muy fácil de entender. Pero, ¿quiere decir que Kleene Star es un operador (como plus es un operador) y el cierre de Kleene es una operación (como una suma)? También la respuesta de Babou de que el nombre proviene del hecho de que la operación representa esencialmente el cierre del conjunto bajo concatenación tiene mucho sentido. ?! Aunque no estropear las cosas épsilon poco allí ...
mallardz
1
@mallardz Hablando correctamente, el cierre es el conjunto; La operación de formar el cierre se denomina normalmente "cierre".
David Richerby
@DavidRicherby: ¿Podría llamar al conjunto de números naturales bajo resta como un cierre ? ¿Quiere decir que dado que el conjunto de expresiones regulares cerradas bajo el operador kleene * produce una expresión regular, lo llamamos cierre?
justin
@justin Por definición, el cierre de cualquier conjunto bajo una operación debe cerrarse bajo esa operación. Dado que los naturales no están cerrados por sustracción, no pueden ser el cierre de nada por sustracción. El conjunto de expresiones regulares ya está cerrado bajo la estrella de Kleene y el cierre del conjunto de expresiones regulares bajo alguna operación es, por definición, un conjunto de cosas, no una sola expresión regular. Así que realmente no entiendo tus preguntas.
David Richerby
@DavidRicherby: Sí, es verdad. Por error, tomé el conjunto de números naturales bajo resta como un número natural completo. ¿Está la estrella de Kleene relacionada con conjuntos o con autómatas finitos o ambos?
justin
7

En una palabra

El nombre de cierre de Kleene está claramente destinado a significar cierre bajo alguna operación de cadena.

Sin embargo, un análisis cuidadoso (gracias a un comentario crítico del OP Mallardz), muestra que la estrella de Kleene no puede cerrarse bajo concatenación, que más bien corresponde al operador Kleene plus.

El operador estrella de Kleene en realidad corresponde a un cierre bajo la operación de potencia derivada de la concatenación.

El nombre de estrella de Kleene proviene de la representación sintáctica de la operación con una estrella *, mientras que el cierre es lo que hace.

Esto se explica más adelante a continuación.
Recuerde que el cierre en general, y la estrella de Kleene en particular, es una operación en conjuntos, aquí en conjuntos de cadenas, es decir, en idiomas. Esto se usará en la explicación.

Cierre de un subconjunto bajo una operación siempre definida

Un conjunto es cerrado bajo algunos n operación ary f si y sólo si f siempre se define para cualquier n tupla de argumentos en C y C = { f ( c 1 , ... , c n ) | c 1 , ... , c nC } .CnffnCC={f(c1,,cn)c1,,cnC}

Extendiendo a conjuntos de valores de la manera habitual, es decir, f ( S 1 , ... , S n ) = { f ( s 1 , ... , s n ) s iS i . 1 i n } podemos reescribir la condición como una ecuación establecida: C = f ( C , ... , C )f

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


C=f(C,,C)

Para un dominio (o conjunto) con una operación f que siempre se define en D , y un conjunto S D , el cierre de S bajo f es el conjunto más pequeño S f que contiene S que satisface la ecuación: S f = { f ( s 1 , ... , s n ) s 1 , ... , s nS f } .DfDSDSfSfSSf={f(s1,,sn)s1,,snSf}

Más tersamente con una ecuación establecida, el cierre de bajo f puede definirse por:Sf

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

Este es un ejemplo de definición de punto menos fijo, a menudo usado en semántica, y también usado en lenguajes formales. Una gramática libre de contexto se puede ver como un sistema de ecuaciones de idiomas (es decir, ecuaciones de conjuntos de cadenas), donde las no-terminales representan variables de lenguaje. La solución con menos punto fijo asocia un lenguaje a cada variable, y el lenguaje así asociado al símbolo inicial es el definido por la gramática CF.

Extendiendo el concepto

El cierre como se definió anteriormente solo tiene la intención de extender un subconjunto en un conjunto mínimo S f tal que la operación f siempre esté definida.SSff

Como señalado por el mallardz OP, esto no es una explicación suficiente, ya que no incluirá la palabra vacía en S f cuando no está ya en S . De hecho, este cierre corresponde a la definición de Kleene plus y no a la estrella de Kleene .ϵSfS+*

En realidad, la idea de cierre puede extenderse o considerarse de diferentes maneras.

  1. Extensión a otras propiedades algebraicas

    En la forma de extenderlo (aunque ya no se llama cierre ) considera más generalmente una extensión a un conjunto tiene propiedades algebraicas específicas con respecto a la operación f .Sff

    Si define como el conjunto más pequeño que contiene S que es un Monoide para la función binaria f , entonces necesita tanto el cierre como un elemento neutro que es la palabra vacía ϵ .SfSfϵ

  2. Extensión a través de una operación derivada

    Hay una segunda forma, que es más adecuadamente un problema de cierre. Cuando define el cierre de , puede considerarlo con respecto a algunos de los argumentos, mientras permite valores de todo el conjunto D para los otros argumentos.SDD

    Considerando (por simplicidad) una función binaria sobre D , puede definir S f , 1 como el conjunto más pequeño que contiene S que satisface la ecuación: S f , 1 = { f ( s 1 , s 2 ) s 1S f , 1s 2D }fDSf,1S

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

    o con ecuaciones establecidas:

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

    Esto también tiene sentido cuando los argumentos no pertenecen al mismo conjunto. Entonces puede cerrar con respecto a algunos argumentos en un conjunto, mientras considera todos los valores posibles para los otros argumentos (son posibles muchas variaciones).

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

    Y esto nos da la operación en estrella de Kleene cuando la construcción se aplica a la operación de concatenación del monoide de cadenas libre.

    Para ser completamente honesto, no estoy seguro de que no haya estado haciendo trampa. Pero una definición es solo lo que haces, y esa fue la única forma en que encontré convertir la estrella de Kleene en un cierre. Puede que me esté esforzando demasiado.
    Comentarios son bienvenidos

Cerrar un conjunto bajo una operación que no siempre está definida

Esta es una visión y uso ligeramente diferentes del concepto de cierre. Este punto de vista no responde realmente a la pregunta, pero parece bueno tenerlo en cuenta para evitar posibles confusiones.

fD

  • Df

  • DDf

  • DDff

DfDf

Así es como se construyen los enteros a partir de números naturales, considerando el conjunto de pares de números naturales cotizados por una relación de equivalencia (dos pares son equivalentes si los dos elementos están en el mismo orden y tienen la misma diferencia).

Así también se pueden construir racionales a partir de los enteros.

Y así es como los reales clásicos se pueden construir a partir de los racionales, aunque la construcción es más compleja.

babou
fuente
Hola, gracias, la explicación de cierre bajo concatenación tiene mucho sentido, pero ¿existe épsilon en el cierre bajo concatenación?
mallardz
ϵ
@DavidRicherby En realidad, lo que quise decir es que si tiene un conjunto S = {m}, ¿el cierre bajo concatenación de S contiene epsilon? Porque m * hace bien? Si no es así, supongo que el cierre de Kleene no es del todo equivalente al cierre bajo concatenación, aunque todavía puedo ver cómo es donde se originó el nombre. ¿También recuerdo haber leído en alguna parte cómo inicialmente la estrella de Kleene era un operador binario y evitaba producir épsilon?
mallardz
@DavidRicherby Completé mi respuesta en un intento de cumplir con la objeción justa de @ mallardz.
babou
6

Otro significado de cierre , que es más general que el significado explicado por David Richerby, es cualquier operador:XX en un poset X que satisface los siguientes axiomas:

  1. XX
  2. XyXy
  3. (X)=X

El ejemplo clásico es el cierre topológico , que también satisface= y (Xy)=Xy, 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Σ. If x,yΣ then xy if xy. The axioms of closure then state that

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

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

Yuval Filmus
fuente
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
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.
babou