Warum wird der Kleene-Star-Operator auch als "Closure" -Operator bezeichnet?

13

Ich habe festgestellt, dass, wenn ich die Etymologie hinter einem CS / Programmierbegriff nicht verstehe, dies normalerweise bedeutet, dass ich ein wichtiges zugrunde liegendes Konzept verpasst oder missverstanden habe.

Ich verstehe nicht, warum der Kleene-Stern auch als Kleene-Verschluss bezeichnet wird. Handelt es sich um Programmierschließungen, eine Funktion mit gebundenen nichtlokalen Variablen?

... bei Überlegungen vielleicht, weil es erlaubt, eine offene Menge in einer geschlossenen Ausdrucksform zu schreiben?

... nun ja, auf eine gute, alte Art und Weise, die Gummi-Enten erklärt , denke ich, dass es das ist, aber ich würde trotzdem eine maßgebliche Antwort begrüßen.

Mallardz
quelle
3
Ist Ihr Benutzername der Grund, warum Sie gute alte Gummi-Enten-erklärende Mode wollen ?
Babou
@babou Ja. Aber es ist mir heute nicht
gelungen
Ihre Bemerkung, dass der in meiner Antwort definierte Abschluss unter Verkettung (und in der Antwort von @David Richerby, der außer in einem Kommentar niemals explizit eine Zeichenfolgenoperation erwähnt) das leere Wort ϵ nicht enthält, ist ziemlich genau. Vielen Dank. Infolgedessen kann der Kleene-Stern-Operator keine Schließung unter Verkettung darstellen: Der Kleene + -Operator tut dies. Der Kleene-Stern-Operator kann jedoch eine Schließung unter der aus der Verkettung abgeleiteten Kraftoperation darstellen. Ich werde meine Antwort ergänzen, um diesen Aspekt abzudecken. Es war subtiler als erwartet.
Babou
Ist die Antwort gut lesbar oder sollte ich einen Abschnitt in weicherem Gummi einfügen?
Babou

Antworten:

15

Ein Satz wird unter einigen Operatoren geschlossen , wenn das Ergebnis der Anwendung des Operators auf Elemente im Satz immer im Satz enthalten ist. Zum Beispiel werden die natürlichen Zahlen unter Hinzufügung geschlossen, weil, wenn und m natürliche Zahlen sind, n + m eine natürliche Zahl ist. Auf der anderen Seite werden die Naturals nicht durch Subtraktion geschlossen, da zum Beispiel 3 - 5 keine natürliche Zahl ist.nmn+m35

Das Schließen einer Menge unter einem Operator ist die kleinste Menge, die S enthält , das unter dem Operator geschlossen ist. Zum Beispiel ist das Schließen der natürlichen Zahlen unter Subtraktion die ganzen Zahlen; Das Schließen der zu addierenden natürlichen Zahlen ist nur die natürliche Zahl, da die Menge bereits geschlossen ist.SS

"Kleene Closure" ist also keine alternative Bezeichnung für "Kleene Star". Der Kleene-Stern ist der Operator; Der Kleene-Abschluss eines Sets ist der Abschluss des Sets unter dem Betreiber.

David Richerby
quelle
Ok, danke, deine Erklärung für die Schließung eines Sets ist sehr einfach zu verstehen. Aber meinst du, Kleene Star ist ein Operator (wie Plus ist ein Operator) und Kleene Closure ist eine Operation (wie Addition)? Auch Babous Antwort, dass der Name von der Tatsache herrührt, dass die Operation im Wesentlichen das Schließen des Satzes unter Verkettung darstellt, ist sehr sinnvoll. Obwohl Epsilon die Dinge dort nicht ein wenig
durcheinander bringt
1
@mallardz Eigentlich ist der Abschluss die Menge; Der Vorgang des Bildens des Verschlusses wird normalerweise als "Schließen" bezeichnet.
David Richerby
@DavidRicherby: Könnten Sie die Menge der natürlichen Zahlen unter Subtraktion als Abschluss bezeichnen ? Wollen Sie damit sagen, dass die Menge der regulären Ausdrücke, die unter dem Operator kleene * geschlossen sind, einen regulären Ausdruck erzeugt, den wir als Abschluss bezeichnen?
Justin
@justin Definitionsgemäß muss das Schließen einer Menge unter einer Operation selbst unter dieser Operation geschlossen werden. Da die Naturalien nicht durch Subtraktion geschlossen werden, können sie nichts durch Subtraktion schließen. Die Menge der regulären Ausdrücke ist bereits unter Kleene Star geschlossen, und die Schließung der Menge der regulären Ausdrücke unter bestimmten Operationen ist per Definition eine Menge von Dingen und kein einziger regulärer Ausdruck. Also verstehe ich deine Fragen nicht wirklich.
David Richerby
@DavidRicherby: Ja, das ist wirklich richtig. Aus Versehen habe ich die Menge der natürlichen Zahlen als ganze natürliche Zahl subtrahiert. Bezieht sich Kleene Star auf Mengen oder auf endliche Automaten oder auf beides?
Justin
7

In einer Nussschale

Der Name Kleene-Verschluss soll eindeutig den Verschluss unter einer Schnuroperation bedeuten .

Eine sorgfältige Analyse (dank eines kritischen Kommentars des OP mallardz) zeigt jedoch, dass der Kleene-Stern nicht unter Verkettung geschlossen werden kann, was eher dem Kleene-Plus-Operator entspricht.

Der Kleene-Sternoperator entspricht tatsächlich einer Schließung unter der aus der Verkettung abgeleiteten Kraftoperation.

Der Name Kleene Stern kommt von der syntaktischen Darstellung der Operation mit einem Stern *, während das Schließen das ist, was es tut.

Dies wird weiter unten erläutert.
Denken Sie daran, dass das Schließen im Allgemeinen und Kleene Star im Besonderen eine Operation an Mengen ist, hier an Mengen von Zeichenketten, dh an Sprachen. Dies wird in der Erklärung verwendet.

Schließen einer Teilmenge unter einer Operation immer definiert

Eine Menge wird unter einer n- jährigen Operation f geschlossen, wenn f immer für ein n- Tupel von Argumenten in C definiert ist und C = { f ( c 1 , , c n ) c 1 , , c nC } .CnffnCC={f(c1,,cn)c1,,cnC}

Durch übliche Erweiterung von auf Wertemengen, dh f ( S 1 , , S n ) = { f ( s 1 , , s n ) s iS i . 1 i n } wir können die Bedingung als gesetzte Gleichung umschreiben: C = f ( C , , C )f

f(S1,,Sn)={f(s1,,sn)sichSich.1ichn}


C=f(C,,C)

Für eine Domäne (oder Menge) mit einer Operation f , die immer für D definiert ist , und einer Menge S D ist der Abschluss von S unter f die kleinste Menge S f, die S enthält und die folgende Gleichung erfüllt: S f = { f ( s 1 , , s n ) s 1 , , s nS f } .DfDSDSfSfSSf={f(s1,,sn)s1,,snSf}

Genauer gesagt, mit einer festen Gleichung kann der Abschluss von unter f definiert werden durch:Sf

Sf ist die kleinste Menge, so dass SSf und Sf=f(Sf,,Sf)

Dies ist ein Beispiel für die am wenigsten festgelegte Definition, die häufig in der Semantik und auch in formalen Sprachen verwendet wird. Eine kontextfreie Grammatik kann als ein System von Sprachgleichungen (dh String-Set-Gleichungen) angesehen werden, bei denen die nicht-terminalen für Sprachvariablen stehen. Die am wenigsten festgelegte Lösung ordnet jeder Variablen eine Sprache zu, und die Sprache, die somit dem Anfangssymbol zugeordnet ist, ist diejenige, die durch die CF-Grammatik definiert ist.

Das Konzept erweitern

Der oben definierte Abschluss soll nur eine Teilmenge in eine minimale Menge S f erweitern, so dass die Operation f immer definiert ist.SSff

Wie von der OP mallardz bemerkt, ist dies keine ausreichende Erklärung, da das leere Wort in S f nicht enthalten ist, wenn es nicht bereits in S enthalten ist . In der Tat entspricht dieser Verschluss der Definition des Kleene-Plus und nicht des Kleene-Sterns .ϵSfS+*

Tatsächlich kann die Idee der Schließung erweitert oder auf unterschiedliche Weise betrachtet werden.

  1. Erweiterung auf andere algebraische Eigenschaften

    Auf dem Weg zu seiner Erweiterung (obwohl es nicht länger als Abschluss bezeichnet wird ) wird allgemein eine Erweiterung auf eine Menge mit spezifischen algebraischen Eigenschaften in Bezug auf die Operation f betrachtet .Sff

    Wenn Sie als die kleinste Menge definieren, die S enthält , das ein Monoid für die Binärfunktion f ist , benötigen Sie sowohl einen Abschluss als auch ein neutrales Element, das das leere Wort ϵ ist .SfSfϵ

  2. Erweiterung durch eine abgeleitete Operation

    Es gibt einen zweiten Weg, der genauer gesagt ein Problem der Schließung ist. Wenn Sie den Abschluss von , können Sie ihn in Bezug auf einige der Argumente berücksichtigen, während Sie Werte aus der gesamten Menge D für die anderen Argumente zulassen .SDD

    Unter Berücksichtigung (der Einfachheit halber) eine binäre Funktion über D können Sie definieren , S f , 1 als die kleinste Menge enthalten , S : daß die Gleichung S f , 1 = { f ( s 1 , s 2 ) | s 1S f , 1s 2D }fDSf,1S

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

    oder mit gesetzten Gleichungen:

    Sf,1 ist die kleinste Menge, so dass SSf,1 und Sf,1=f(Sf,1,D)

    Dies ist auch dann sinnvoll, wenn die Argumente nicht zur gleichen Menge gehören. Dann haben Sie möglicherweise einen Abschluss in Bezug auf einige Argumente in einem Satz, während Sie alle möglichen Werte für die anderen Argumente berücksichtigen (viele Variationen sind möglich).

    (M,f,ϵ) --fMϵuM

    uM.u0=ϵ und nNun=f(u,un-1)

    unMN0

    MnUn={unuU}unf

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

    U,1UM

    U,1 ist die kleinste Menge solcher UU,1 und U,1=f(U,1,N0)

    Und dies gibt uns die Kleene-Stern-Operation, wenn die Konstruktion auf die Verkettungsoperation des freien Monoids von Zeichenfolgen angewendet wird.

    Um ganz ehrlich zu sein, bin ich mir nicht sicher, ob ich nicht betrogen habe. Aber eine Definition ist nur das, was Sie daraus machen, und nur so konnte ich den Kleene-Stern tatsächlich in einen Verschluss verwandeln. Ich versuche es vielleicht zu sehr.
    Kommentare sind willkommen.

Schließen eines Sets unter einer Operation, die nicht immer definiert ist

Dies ist eine etwas andere Ansicht und Verwendung des Konzepts der Schließung. Diese Ansicht beantwortet die Frage nicht wirklich, aber es scheint gut, sie im Hinterkopf zu behalten, um mögliche Verwirrungen zu vermeiden.

fD

  • Df

  • DDf

  • DDff

DfDf

Auf diese Weise werden Ganzzahlen aus natürlichen Zahlen gebildet, wobei die Menge der natürlichen Zahlenpaare berücksichtigt wird, die durch eine Äquivalenzrelation ausgedrückt werden (zwei Paare sind äquivalent, wenn sich die beiden Elemente in derselben Reihenfolge befinden und denselben Unterschied aufweisen).

Auf diese Weise können auch Rationalen aus den ganzen Zahlen gebildet werden.

Und so können klassische Realitäten aus den Rationalitäten gebaut werden, obwohl die Konstruktion komplexer ist.

babou
quelle
Hey danke, der Abschluss unter Verkettung Erklärung macht viel Sinn, aber existiert in dem Abschluss unter Verkettung Epsilon?
Mallardz
ϵ
@DavidRicherby Eigentlich meinte ich, wenn Sie eine Menge S = {m} haben, enthält dann der Abschluss unter Verkettung von S epsilon? Weil m * es richtig macht? Wenn nicht, dann ist Kleene Closure wohl nicht ganz gleichbedeutend mit Closure under Concatenation, obwohl ich immer noch sehen kann, woher der Name stammt. Ich erinnere mich auch, dass ich irgendwo gelesen habe, wie Kleene Star anfangs ein binärer Operator war und es vermieden hat, Epsilon zu produzieren.
Mallardz
@DavidRicherby Ich habe meine Antwort vervollständigt, um dem fairen Einwand von @ mallardz zu begegnen.
Babou
6

:XXX

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

Das klassische Beispiel ist die topologische Schließung , die auch erfüllt=(xy)=xy

X=2Σx,yΣxyxy

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

Der Kleene-Plus-Operator erfüllt auch diese Axiome und ist daher auch ein Closure-Operator im Sinne dieser Definition.

Yuval Filmus
quelle
Entfernt dies nicht die Minimalanforderung? Ich meine, wenn Sie diese Anforderung entfernen, sind sowohl die Antwort von David Richerby als auch meine ursprüngliche Antwort für den Kleene-Stern in Ordnung.
Babou
Ich beantworte meinen eigenen Kommentar. Die Minimalität wird beibehalten, aber in Bezug auf die Menge der geschlossenen Mengen definiert. Keine direkte Beziehung zu einer Operation für Zeichenfolgen wie Verkettung. Kleene star und plus sind dann beide Schließvorgänge, werden jedoch unter Verwendung der Minimalität in Bezug auf verschiedene Sätze von geschlossenen Sätzen definiert. Dies ist eine viel abstraktere Sichtweise. (Zumindest habe ich die Befriedigung zu sehen, dass es der richtige Weg war, sich wieder auf dem festgelegten Niveau zu befinden, wie ich es endlich getan habe :). Interessant. Vielen Dank.
Babou