Dlaczego operator gwiazdy Kleene jest również nazywany operatorem „zamykania” Kleene?

Przekonałem się, że jeśli nie rozumiem etymologii kryjącej się za terminem cs / programowanie, zwykle oznacza to, że przeoczyłem lub źle zrozumiałem jakąś ważną koncepcję.

Nie rozumiem, dlaczego gwiazda Kleene jest również nazywana zamknięciem Kleene. Czy ma to związek z zamknięciami w programowaniu, funkcją ze związanymi zmiennymi nielokalnymi?

... po zastanowieniu, może dlatego, że pozwala na napisanie zbioru otwartego w formie wyrażenia zamkniętego?

... no cóż, w dobrym, starym stylu wyjaśniającym gumową kaczkę , domyślam się, że o to chodzi, ale nadal chętnie przyjmę wiarygodną odpowiedź.

Zestaw jest zamykany przez jakiegoś operatora, jeśli wynik zastosowania operatora do rzeczy w zestawie jest zawsze w zestawie. Na przykład liczby naturalne są zamknięte podczas dodawania, ponieważ za każdym razem, gdy i m są liczbami naturalnymi, n + m jest liczbą naturalną. Z drugiej strony, naturals nie są zamknięte odejmowanie, ponieważ na przykład 3 - 5 nie jest liczbą naturalną.$n$$m$$n+m$$3-5$

Zamknięcie z ustalonym pod pewnym operatora jest najmniejszy zestaw zawierający S , który jest zamknięty pod operatora. Na przykład zamknięcie odejmowanych liczb naturalnych jest liczbami całkowitymi; zamknięcie dodawanych liczb naturalnych jest tylko liczbami naturalnymi, ponieważ zestaw jest już zamknięty.$S$$S$

Tak więc „zamknięcie Kleene” nie jest alternatywną nazwą dla „gwiazdy Kleene”. Gwiazdą Kleene jest operator; zamknięcie Kleene zestawu jest zamknięciem tego zestawu pod operatorem.

W skrócie

Nazwa zamknięcie Kleene ma wyraźnie oznaczać zamknięcie w przypadku niektórych operacji łańcuchowych.

Jednak dokładna analiza (dzięki krytycznemu komentarzowi OP mallardz) pokazuje, że gwiazda Kleene nie może być zamknięta podczas konkatenacji, co raczej odpowiada operatorowi Kleene plus.

Operator gwiazdy Kleene w rzeczywistości odpowiada zamknięciu pod operacją mocy pochodzącą z konkatenacji.

Nazwa gwiazda Kleene pochodzi od syntaktycznego przedstawienia operacji z gwiazdą *, podczas gdy zamknięcie jest tym, co robi.

Jest to wyjaśnione poniżej.
Przypomnijmy, że zamknięcie w ogóle, a zwłaszcza gwiazda Kleene, jest operacją na zbiorach, tutaj na zbiorach ciągów, tj. Na językach. Zostanie to wykorzystane w wyjaśnieniu.

Zamknięcie podzbioru w ramach operacji zawsze zdefiniowane

$C$$n$$f$$f$$n$$C$$C=\{f(c_1,\ldots,c_n)\mid \forall c_1,\ldots,c_n \in C\}$

$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\}$

$S$$f$

Jest to przykład definicji o najmniej ustalonym punkcie, często używanej w semantyce, a także używanej w językach formalnych. Gramatyka bezkontekstowa może być postrzegana jako układ równań języków (tj. Równań ciągów znaków), gdzie nieterminalne oznaczają zmienne językowe. Najmniej rozwiązywanym punktem kojarzy język z każdą zmienną, a językiem związanym w ten sposób z symbolem początkowym jest język zdefiniowany przez gramatykę CF.

Rozszerzenie koncepcji

$S$$S_f$$f$

$\epsilon$$S_f$$S$+*

W rzeczywistości pomysł zamknięcia można rozszerzyć lub rozważyć na różne sposoby.

1. Rozszerzenie na inne właściwości algebraiczne

   $S_f$$f$

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

2. Rozszerzenie poprzez operację pochodną

   $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\}$$

   lub z ustalonymi równaniami:

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

   Ma to również sens, gdy argumenty nie należą do tego samego zestawu. Wtedy możesz mieć zamknięcie w odniesieniu do niektórych argumentów w jednym zestawie, biorąc pod uwagę wszystkie możliwe wartości dla innych argumentów (możliwych jest wiele odmian).

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

   To daje nam operację gwiazdy Kleene, gdy konstrukcja jest zastosowana do operacji konkatenacji wolnego Monoidu z łańcuchów.

   Szczerze mówiąc, nie jestem pewien, czy nie oszukiwałem. Ale definicja jest tylko tym, co stworzysz, i to był jedyny sposób, w jaki znalazłem sposób, aby zmienić gwiazdę Kleene w zamknięcie. Być może próbuję zbyt mocno.
   _{Komentarze są mile widziane.}

Zamykanie zestawu w ramach operacji, która nie zawsze jest zdefiniowana

Jest to nieco inny pogląd i zastosowanie koncepcji zamknięcia. Ten pogląd tak naprawdę nie odpowiada na pytanie, ale wydaje się, że warto o tym pamiętać, aby uniknąć pewnych nieporozumień.

$f$$D$

• $D$$f$

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

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

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

Tak buduje się liczby całkowite z liczb naturalnych, biorąc pod uwagę zestaw par liczb naturalnych ilorazowych przez relację równoważności (dwie pary są równoważne, jeśli dwa elementy są w tej samej kolejności i mają tę samą różnicę).

W ten sposób można również tworzyć racjonalne liczby całkowite.

I w ten sposób można zbudować klasyczne realia z racjonalności, chociaż konstrukcja jest bardziej złożona.

$\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^*$

Operator Kleene plus również spełnia te aksjomaty, więc jest również operatorem zamknięcia zgodnie z tą definicją.