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

13

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

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

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

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

mallardz
источник
3
Ваше имя пользователя - причина, по которой вы хотите старую добрую манеру, объясняющую резиновые утки ?
Бабу
@babou Да. Но это
подвело
Ваше замечание о том, что замыкание при конкатенации, определенное в моем ответе (и в ответе @David Richerby, неявно, поскольку он никогда не упоминает явно о какой-либо строковой операции, за исключением комментария), не будет включать пустое слово ϵ, довольно точно. Благодарю. Как следствие, оператор звезды Клини не может представлять замыкание при конкатенации, как оператор Клини +. Однако оператор звезды Клини может представлять замыкание при силовой операции, полученной в результате конкатенации. Я дополняю свой ответ, чтобы охватить этот аспект. Это было более тонким, чем ожидалось.
Бабу
Достаточно ли понятен ответ, или я должен добавить раздел из более мягкой резины?
Бабу

Ответы:

15

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

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

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

Дэвид Ричерби
источник
Хорошо, спасибо, ваше объяснение закрытия набора очень легко понять. Но вы имеете в виду, что звезда Клини - это оператор (как плюс - оператор), а закрытие Клини - это операция (как сложение)? Ответ Бабу о том, что название происходит от того факта, что операция, по сути, представляет собой закрытие конкатенации, имеет большой смысл. Хотя эпсилон там немного не
портит
1
@mallardz Собственно говоря, замыкание - это множество; Операция формирования закрытия обычно называется «закрытием».
Дэвид Ричерби
@DavidRicherby: Не могли бы вы назвать множество натуральных чисел при вычитании как замыканию ли вы сказать , что , поскольку множество регулярных выражений замкнуто относительно оператора? Клини * производит регулярное выражение , которое мы называем этим замыканием?
Джастин
@justin По определению, закрытие любого множества в операции должно быть само закрыто в этой операции. Поскольку натуральные объекты не замкнуты вычитанием, они не могут быть замыканием чего-либо при вычитании. Множество регулярных выражений уже закрыто под звездой Клини, и замыкание множества регулярных выражений для некоторой операции по определению является набором вещей, а не одним регулярным выражением. Поэтому я не очень понимаю ваши вопросы.
Дэвид Ричерби
@DavidRicherby: Да, это действительно так. По ошибке я взял вычитание набора натуральных чисел как целого натурального числа. Звезда Клини связана с множествами или с конечными автоматами или с обоими?
Джастин
7

В двух словах

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

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

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

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

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

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

Множество замкнуто относительно некоторых п - арной операции F тогда и только тогда е всегда определяется для любого п -кратного аргументов в C и C = { F ( с 1 , ... , с п ) | с 1 , ... , с пC } .CnffnCC={f(c1,,cn)c1,,cnC}

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

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


C=f(C,,C)

Для области (или множества) с операцией f, которая всегда определяется на D , и множеством S D , замыкание S в f является наименьшим множеством S f, содержащим S, которое удовлетворяет уравнению: S f = { f ( s 1 , , s n ) s 1 , , s nS f } .DfDSDSfSfSSf={f(s1,,sn)s1,,snSf}

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

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

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

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

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

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

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

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

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

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

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

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

    Рассматривая (для простоты) двоичную функцию над D , вы можете определить S f , 1 как наименьшее множество, содержащее S , удовлетворяющее уравнению: S f , 1 = { f ( s 1 , s 2 ) s 1S е , 1s 2D }fDSf,1S

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

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

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

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

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

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

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

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

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

fD

  • Df

  • DDf

  • DDff

DfDf

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

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

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

Babou
источник
Эй, спасибо, объяснение замыкания при конкатенации имеет большой смысл, но существует ли эпсилон в замыкании при конкатенации?
Маллардз
ϵ
@DavidRicherby На самом деле я имел в виду, что если у вас есть набор S = {m}, то содержит ли замыкание при конкатенации S эпсилон? Потому что м * правильно? Если нет, то я предполагаю, что замыкание Клини не совсем эквивалентно закрытию при конкатенации, хотя я все еще могу видеть, как именно отсюда и произошло название. Также я помню, что где-то читал, как изначально Kleene star была бинарным оператором и избегала производить эпсилон?
Маллардз
@DavidRicherby Я завершил свой ответ, пытаясь удовлетворить справедливое возражение @ mallardz.
Бабу
6

Другим значением замыкания , которое является более общим, чем значение, объясненное Дэвидом Ричерби, является любой оператор*:ИксИкс на сцене Икс это удовлетворяет следующим аксиомам:

  1. ИксИкс*
  2. ИксYИкс*Y*
  3. (Икс*)*знак равноИкс*

Классическим примером является топологическое замыкание , которое также удовлетворяет*знак равно и (ИксY)*знак равноИкс*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Σ. 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
источник
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