Звезда́ Кли́ни (или замыка́ние Кли́ни) в математической логике и информатике — унарная операция над множеством строк либо символов. Замыкание Клини множества V обозначается V*. Широко применяется в регулярных выражениях, на примере которых было введено Стивеном Клини для описания некоторых автоматов.
Если V — множество строк то V* — минимальное надмножество множества V, которое содержит ε (пустую строку (англ.)) и замкнуто относительно конкатенации. Это также множество всех строк, полученных конкатенацией нуля или более строк из V. Если V — множество символов то V* — множество всех строк из символов из V с добавлением пустой строки.
Содержание
Определение
Степень множества
Нулевая степень любого множества неизменна:
.
Остальные степени определяются рекурсивно:
Звезда Клини
Замыкание Клини множества V есть
.
Плюс Клини
Есть операция, аналогичная звезде Клини, — плюс Клини:
.
Свойства
Примеры
Обобщение
Литература
См. также
Полезное
Смотреть что такое «Замыкание Клини» в других словарях:
Замыкание — В Викисловаре есть статья «замыкание» Замыкание процесс или результат действия, сводящегося к ограничению или спрямлению чего либо … Википедия
Звезда Клини — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете … Википедия
Звёздочка Клини — Звезда Клини (или замыкание Клини) в математической логике и информатике унарная операция над множеством строк либо символов. Замыкание Клини множества V обозначается V*. Широко применяется в регулярных выражениях, на примере которых было введено … Википедия
Плюс Клини — Звезда Клини (или замыкание Клини) в математической логике и информатике унарная операция над множеством строк либо символов. Замыкание Клини множества V обозначается V*. Широко применяется в регулярных выражениях, на примере которых было введено … Википедия
Регулярные выражения — (англ. regular expressions, сокр. RegExp, RegEx, жарг. регэкспы или регексы) это формальный язык поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов (символов джокеров,… … Википедия
Регексп — Регулярные выражения (англ. regular expressions, сокр. RegExp, RegEx, жарг. регэкспы или регексы) система синтаксического разбора текстовых фрагментов по формализованному шаблону, основанная на системе записи образцов для поиска. Образец (англ.… … Википедия
Регексы — Регулярные выражения (англ. regular expressions, сокр. RegExp, RegEx, жарг. регэкспы или регексы) система синтаксического разбора текстовых фрагментов по формализованному шаблону, основанная на системе записи образцов для поиска. Образец (англ.… … Википедия
Регеспы — Регулярные выражения (англ. regular expressions, сокр. RegExp, RegEx, жарг. регэкспы или регексы) система синтаксического разбора текстовых фрагментов по формализованному шаблону, основанная на системе записи образцов для поиска. Образец (англ.… … Википедия
Регулярки — Регулярные выражения (англ. regular expressions, сокр. RegExp, RegEx, жарг. регэкспы или регексы) система синтаксического разбора текстовых фрагментов по формализованному шаблону, основанная на системе записи образцов для поиска. Образец (англ.… … Википедия
Регулярное выражение — Регулярные выражения (англ. regular expressions, сокр. RegExp, RegEx, жарг. регэкспы или регексы) система синтаксического разбора текстовых фрагментов по формализованному шаблону, основанная на системе записи образцов для поиска. Образец (англ.… … Википедия
Замкнутость КС-языков относительно различных операций
В отличие от регулярных языков, КС-языки не замкнуты относительно всех теоретико-множественных операций. К примеру, дополнение и пересечение КС-языков не обязательно являются КС-языками.
Здесь и далее считаем, что [math] L_1 [/math] и [math] L_2 [/math] — КС-языки.
Содержание
Операции с КС-языками [ править ]
Объединение [ править ]
Конкатенация [ править ]
Замыкание Клини [ править ]
Гомоморфизмы [ править ]
Прямой гомоморфизм [ править ]
Обратный гомоморфизм [ править ]
Докажем аналогично соответствующему утверждению для регулярных языков. Построим МП-автомат для [math] \mathrm>(L) = \< w \mid \mathrm(w) \in L \> [/math] на основе МП-автомата для языка [math] L [/math] (назовем его [math] M [/math] ). Новый автомат [math] M’ [/math] будет действовать следующим образом:
Разворот [ править ]
Доказательство аналогично.
[math]\triangleleft[/math]
Пусть задана КС-грамматика [math]G[/math] для языка [math]L = a^i b^j c^i[/math] со следующими правилами:
В таком случае КС-грамматика [math]G^R[/math] для языка [math]L^R = c^i b^j a^i [/math] выглядит следующим образом:
Дополнение к языку тандемных повторов [ править ]
[math]\triangleright[/math]
Это доказывается с помощью леммы о разрастании.
[math]\triangleleft[/math]
Утверждение:
Для правила [math]S \to BA [/math] доказательство аналогично.
Пересечение [ править ]
По замкнутости КС-языков относительно конкатенации получаем, что [math] L_1 [/math] и [math] L_2 [/math] являются КС-языками.
Более того, задачи определения того, является ли дополнение КС-языка КС-языком и проверки непустоты пересечения КС-языков являются алгоритмически неразрешимыми.
Половины тандемных повторов [ править ]
Заметим, что он может быть сгенерирован при помощи следующей КС-грамматики:
Докажем, что [math] \mathrm(L) [/math] не является КС-языком.
Операции над КС-языком и регулярным языком [ править ]
Пересечение [ править ]
Построим МП-автомат для пересечения регулярного языка и КС-языка.
Пусть регулярный язык задан своим ДКА, а КС-язык — своим МП-автоматом c допуском по допускающему состоянию. Построим прямое произведение этих автоматов так же, как строилось прямое произведение для двух ДКА.
видя на ленте символ [math] c [/math] и символ [math] d [/math] на вершине стека.
Звезда́ Кли́ни (или замыка́ние Кли́ни) в математической логике и информатике — унарная операция над множеством строк либо символов. Замыкание Клини множества V обозначается V*. Широко применяется в регулярных выражениях, на примере которых было введено Стивеном Клини для описания некоторых автоматов.
Если V — множество строк то V* — минимальное надмножество множества V, которое содержит ε (пустую строку (англ.)) и замкнуто относительно конкатенации. Это также множество всех строк, полученных конкатенацией нуля или более строк из V. Если V — множество символов то V* — множество всех строк из символов из V с добавлением пустой строки.
Содержание
Определение
Степень множества
Нулевая степень любого множества неизменна:
.
Остальные степени определяются рекурсивно:
Звезда Клини
Замыкание Клини множества V есть
.
Плюс Клини
Есть операция, аналогичная звезде Клини, — плюс Клини:
.
Свойства
Примеры
Обобщение
Литература
См. также
Полезное
Смотреть что такое «Плюс Клини» в других словарях:
Звезда Клини — В этой статье не хватает ссылок на источники информации. Информация должна быть проверяема, иначе она может быть поставлена под сомнение и удалена. Вы можете … Википедия
Замыкание Клини — Звезда Клини (или замыкание Клини) в математической логике и информатике унарная операция над множеством строк либо символов. Замыкание Клини множества V обозначается V*. Широко применяется в регулярных выражениях, на примере которых было введено … Википедия
Звёздочка Клини — Звезда Клини (или замыкание Клини) в математической логике и информатике унарная операция над множеством строк либо символов. Замыкание Клини множества V обозначается V*. Широко применяется в регулярных выражениях, на примере которых было введено … Википедия
Модель акторов — В компьютерных науках модель акторов представляет собой математическую модель параллельных вычислений, которая трактует понятие «актор» как универсальный примитив параллельного численного расчёта: в ответ на сообщения, которые он получает, актор… … Википедия
АЛГЕБРА ЛОГИКИ — система алгебраич. методов решения логич. задач, а также совокупность задач, решаемых такими методами. А. л. в узком смысле слова алгебраич. (табличное, матричное) построение классич. логики высказываний, в котором рассматриваются… … Философская энциклопедия
Регулярные выражения — (англ. regular expressions, сокр. RegExp, RegEx, жарг. регэкспы или регексы) это формальный язык поиска и осуществления манипуляций с подстроками в тексте, основанный на использовании метасимволов (символов джокеров,… … Википедия
КОНСТРУКТИВНАЯ СЕМАНТИКА — совокупность способов понимания суждений в конструктивной математике. Необходимость в особой семантике вызвана различием общих принципов, лежащих в основе традиционной (классической) и конструктивной математики (далее последний термин будет в… … Математическая энциклопедия
Список статей по математической логике — Это служебный список статей, созданный для координации работ по развитию темы. Данное предупреждение не ус … Википедия
Немного терминологии для тех, кто позабыл ее с младших курсов.
Пусть w — слово (строка из символов над заданным алфавитом, возможно пустая). Обозначение есть количество вхождений символа a в строку w (целое неотрицательное число).
Пусть W — множество слов. Множество слов еще называют языком. Тогда W * — так называемая «звездочка Клини», или «замыкание Клини». Это множество всех слов, которые могут получиться из данных путем разнообразных приписываний их друг к другу множество раз (возможно 0 раз, тогда получится пустая строка). Например, <"foo", "bar">* = Как видно, в этом случае множество получилось бесконечное.
Что такое конечный автомат, воспринимающий заданный язык, я здесь объяснять не буду, долго. Предположим, что читатели это уже знают 🙂
Так вот, задача: над алфавитом из двух символов a, b построить конечный автомат, воспринимающий следующий язык:
Другими словами: замыкание Клини такого множества, которое содержит все такие строки, в которых количество вхождений символа a не равно количеству вхождений символа b.
Смело приглашаю пробовать и делиться решениями в комментариях 😉 Правильные ответы скринятся. Простой онлайновый редактор, который упростит вам рисование автоматов и вставку картинок — yEd.
UPD: Уже много правильных ответов, открываю. Да, это действительно все строки, даже пустая (ибо пустая строка по определению входит в замыкание Клини любого множества). Тысячу и одно доказательство найдете в комментариях.
Почему звездный оператор Клини также называется оператором замыкания Клини?
Я обнаружил, что если я не понимаю этимологию термина «cs / программирования», это обычно означает, что я пропустил или неправильно понял какую-то важную базовую концепцию.
Я не понимаю, почему звезду Клини также называют закрытием Клини. Связано ли это с замыканиями в программировании, функцией со связанными нелокальными переменными?
. если задуматься, может быть, это потому, что он позволяет писать открытый набор в закрытом выражении?
В двух словах
Название Kleene замыкание явно предназначено для обозначения замыкания при какой-либо строковой операции.
Однако тщательный анализ (благодаря критическому комментарию О.П. Малларда) показывает, что звезда Клини не может быть замыканием при конкатенации, что скорее соответствует оператору Клини плюс.
Звездный оператор Клини фактически соответствует замыканию под действием мощности, полученному в результате конкатенации.
Это дополнительно объясняется ниже. Напомним, что замыкание вообще, и звезда Клини в частности, является операцией над множествами, здесь над множествами строк, то есть над языками. Это будет использовано в объяснении.
Закрытие подмножества в операции всегда определяется
Более кратко с заданным уравнением, замыкание под f может быть определено как: S ‘ role=»presentation»> S f ‘ role=»presentation»> f
Это пример определения с наименьшей фиксированной точкой, часто используемый в семантике, а также используемый в формальных языках. Не зависящую от контекста грамматику можно рассматривать как систему уравнений языка (то есть уравнений набора строк), где нетерминальные обозначают языковые переменные. Наименьшее решение с фиксированной запятой связывает язык с каждой переменной, и язык, таким образом связанный с начальным символом, является языком, определенным грамматикой CF.
Расширение концепции
На самом деле, идея закрытия может быть расширена или рассмотрена по-разному.
Распространение на другие алгебраические свойства
Расширение через производную операцию
или с заданными уравнениями:
Это также имеет смысл, когда аргументы не принадлежат одному и тому же набору. Тогда у вас может быть замыкание в отношении некоторых аргументов в одном наборе при рассмотрении всех возможных значений для других аргументов (возможны многие варианты).
u n ‘ role=»presentation»> u n M ‘ role=»presentation»> M N 0 ‘ role=»presentation»> N 0
M ‘ role=»presentation»> M n ‘ role=»presentation»> n U n = < u n ∣ u ∈ U >‘ role=»presentation»> U n = < u n ∣ u ∈ U >u n ‘ role=»presentation»> u n f ‘ role=»presentation»> f
И это действительно дает нам операцию звезды Клини, когда конструкция применяется к операции конкатенации свободного моноида струн.
Закрытие набора в операции, которая не всегда определена
Это немного другой взгляд и использование концепции закрытия. Эта точка зрения на самом деле не отвечает на этот вопрос, но, похоже, следует помнить об этом, чтобы избежать возможных путаницы.
f ‘ role=»presentation»> f D ‘ role=»presentation»> D
D ‘ role=»presentation»> D f ‘ role=»presentation»> f
D ′ ‘ role=»presentation»> D ′ D ‘ role=»presentation»> D f ′ ‘ role=»presentation»> f ′
D ‘ role=»presentation»> D D ′ ‘ role=»presentation»> D ′ f ‘ role=»presentation»> f f ′ ‘ role=»presentation»> f ′
D ′ ‘ role=»presentation»> D ′ f ′ ‘ role=»presentation»> f ′ D ‘ role=»presentation»> D f ‘ role=»presentation»> f
Таким образом, целые числа строятся из натуральных чисел, учитывая набор пар натуральных чисел, квотированных отношением эквивалентности (две пары эквивалентны, если два элемента находятся в одном и том же порядке и имеют одинаковую разницу).
Это также, как рациональные числа могут быть построены из целых чисел.
И вот как классические реалы могут быть построены из рациональных, хотя строительство является более сложным.
.
.
.
