Почему звездный оператор Клини также называется оператором замыкания Клини?

Я обнаружил, что если я не понимаю этимологию термина «cs / программирования», это обычно означает, что я пропустил или неправильно понял какую-то важную базовую концепцию.

Я не понимаю, почему звезду Клини также называют закрытием Клини. Связано ли это с замыканиями в программировании, функцией со связанными нелокальными переменными?

... если задуматься, может быть, это потому, что он позволяет писать открытый набор в закрытом выражении?

... хорошо в старой доброй манере объяснения резиновой утки , теперь я догадываюсь, что это так, но все равно приветствую авторитетный ответ.

Множество замкнуто относительно некоторого оператора, если результат применения оператора к вещам в наборе всегда находится в наборе. Например, натуральные числа закрыты при сложении, потому что, когда и m являются натуральными числами, n + m является натуральным числом. С другой стороны, натуральные числа не вычитаются при вычитании, поскольку, например, 3 - 5 не является натуральным числом.$n$$m$$n+m$$3-5$

Замыкание некоторого множества под некоторым оператором является наименьшим множество , содержащее S , замкнутое относительно оператора. Например, замыкание натуральных чисел при вычитании - это целые числа; замыкание добавляемых натуральных чисел - это просто натуральные числа, так как множество уже закрыто.$S$$S$

Таким образом, «Закрытие Клини» не является альтернативным названием для «Звезды Клини». Клини звезда является оператором; замыкание Клина множества - это замыкание множества под оператором.

В двух словах

Название Kleene замыкание явно предназначено для обозначения замыкания при какой-либо строковой операции.

Однако тщательный анализ (благодаря критическому комментарию О.П. Малларда) показывает, что звезда Клини не может быть замыканием при конкатенации, что скорее соответствует оператору Клини плюс.

Звездный оператор Клини фактически соответствует замыканию под действием мощности, полученному в результате конкатенации.

Название Kleene star происходит от синтаксического представления операции со звездой *, тогда как замыкание - это то, что она делает.

Это дополнительно объясняется ниже.
Напомним, что замыкание вообще, и звезда Клини в частности, является операцией над множествами, здесь над множествами строк, то есть над языками. Это будет использовано в объяснении.

Закрытие подмножества в операции всегда определяется

Множество замкнуто относительно некоторых п - арной операции F тогда и только тогда е всегда определяется для любого п -кратного аргументов в C и C = { F ( с 1 , ... , с п ) | ∀ с 1 , ... , с п ∈ C } .$C$$n$$f$$f$$n$$C$$C=\{f(c_1,\ldots,c_n)\mid \forall c_1,\ldots,c_n \in C\}$

Расширяя к наборам значений обычным способом, то есть п ( S 1 , ... , S п ) = { F ( s 1 , ... , ев н ) | ∀ s я ∈ S я . 1 ≤ i ≤ n } мы можем переписать условие в виде заданного уравнения: C = f ( C , … , C $f$

Для области (или множества) с операцией f, которая всегда определяется на D , и множеством S ⊂ D , замыкание S в f является наименьшим множеством S f, содержащим S, которое удовлетворяет уравнению: 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\}$

Более кратко с заданным уравнением, замыкание под f может быть определено как:$S$$f$

Это пример определения с наименьшей фиксированной точкой, часто используемый в семантике, а также используемый в формальных языках. Не зависящую от контекста грамматику можно рассматривать как систему уравнений языка (то есть уравнений набора строк), где нетерминальные обозначают языковые переменные. Наименьшее решение с фиксированной запятой связывает язык с каждой переменной, и язык, таким образом связанный с начальным символом, является языком, определенным грамматикой CF.

Расширение концепции

Замыкание, как определено выше, предназначено только для расширения подмножества в минимальный набор S f , так что операция f всегда определяется.$S$$S_f$$f$

Как отмечает ОП mallardz, это не является достаточным объяснением, так как она не будет включать в себя пустое слово в S е , когда он уже не в S . Действительно, это замыкание соответствует определению плюса Клини, а не звезде Клини .$\epsilon$$S_f$$S$+*

На самом деле, идея закрытия может быть расширена или рассмотрена по-разному.

1. Распространение на другие алгебраические свойства

   При способе его расширения (хотя оно больше не называется замыканием ) рассматривается более общее расширение множества имеющего определенные алгебраические свойства в отношении операции f .$S_f$$f$

   Если вы определите как наименьшее множество, содержащее S, которое является моноидом для двоичной функции f , то вам потребуется и замыкание, и нейтральный элемент, который является пустым словом ϵ .$S_f$$S$$f$$\epsilon$

2. Расширение через производную операцию

   Есть второй способ, который является более правильным вопросом закрытия. Когда вы определяете замыкание , вы можете рассматривать его в отношении некоторых аргументов, в то время как вы разрешаете значения из всего набора D для других аргументов.$S\subset D$$D$

   Рассматривая (для простоты) двоичную функцию над D , вы можете определить S f , 1 как наименьшее множество, содержащее S , удовлетворяющее уравнению: S f , 1 = { f ( s 1 , s 2 ) ∣ ∀ s 1 ∈ S е , 1 ∧ ∀ s 2 ∈ 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\}$$

   или с заданными уравнениями:

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

   Это также имеет смысл, когда аргументы не принадлежат одному и тому же набору. Тогда у вас может быть замыкание в отношении некоторых аргументов в одном наборе при рассмотрении всех возможных значений для других аргументов (возможны многие варианты).

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

   И это действительно дает нам операцию звезды Клини, когда конструкция применяется к операции конкатенации свободного моноида струн.

   Честно говоря, я не уверен, что я не изменял. Но определение - это только то, что вы делаете, и это был единственный способ, который я нашел, чтобы фактически превратить звезду Клини в замыкание. Возможно, я слишком стараюсь.
   _{Комментарии приветствуются.}

Закрытие набора в операции, которая не всегда определена

Это немного другой взгляд и использование концепции закрытия. Эта точка зрения на самом деле не отвечает на этот вопрос, но, похоже, следует помнить об этом, чтобы избежать возможных путаницы.

$f$$D$

• $D$$f$

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

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

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

Таким образом, целые числа строятся из натуральных чисел, учитывая набор пар натуральных чисел, квотированных отношением эквивалентности (две пары эквивалентны, если два элемента находятся в одном и том же порядке и имеют одинаковую разницу).

Это также, как рациональные числа могут быть построены из целых чисел.

И вот как классические реалы могут быть построены из рациональных, хотя строительство является более сложным.

Другим значением замыкания , которое является более общим, чем значение, объясненное Дэвидом Ричерби, является любой оператор$\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^*$, 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^{\Sigma^*}$. If $x,y \subseteq \Sigma^*$ then $x \leq y$ if $x \subseteq y$. The axioms of closure then state that

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

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