Клини звезда

Унарная операция над наборами строк

В математической логике и информатике звезда Клини (или оператор Клини , или замыкание Клини ) — это унарная операция , выполняемая либо над наборами строк , либо над наборами символов или символов. В математике она более известна как конструкция свободного моноида . Применение звезды Клини к множеству записывается как . Он широко используется для регулярных выражений , в контексте которого он был введен Стивеном Клини для характеристики определенных автоматов , где он означает «ноль или более повторений». ${\displaystyle V}$ ${\displaystyle V^{*}}$

1. Если это набор строк, то он определяется как наименьшее надмножество , содержащее пустую строку и закрывающееся при операции конкатенации строк . ${\displaystyle V}$ ${\displaystyle V^{*}}$ ${\displaystyle V}$ ${\displaystyle \varepsilon }$
2. Если — набор символов или символов, то — это набор всех строк над символами в , включая пустую строку . ${\displaystyle V}$ ${\displaystyle V^{*}}$ ${\displaystyle V}$ ${\displaystyle \varepsilon }$

Набор также можно описать как набор, содержащий пустую строку и все строки конечной длины, которые могут быть сгенерированы путем объединения произвольных элементов , что позволяет использовать один и тот же элемент несколько раз. Если это либо пустое множество ∅, либо одноэлементное множество , то ; если есть любое другое конечное множество или счетно-бесконечное множество , то это счетно-бесконечное множество. ^[1] Как следствие, каждый формальный язык над конечным или счетно-бесконечным алфавитом счетен, поскольку он является подмножеством счетно-бесконечного множества . ${\displaystyle V^{*}}$ ${\displaystyle V}$ ${\displaystyle V}$ ${\displaystyle \{\varepsilon \}}$ ${\displaystyle V^{*}=\{\varepsilon \}}$ ${\displaystyle V}$ ${\displaystyle V^{*}}$ ${\displaystyle \Sigma }$ ${\displaystyle \Sigma ^{*}}$

Операторы используются в правилах перезаписи порождающих грамматик .

Определение и обозначения

Учитывая набор , определите ${\displaystyle V}$

${\displaystyle V^{0}=\{\varepsilon \}}$(язык, состоящий только из пустой строки),

${\displaystyle V^{1}=V}$,

и рекурсивно определим множество

${\displaystyle V^{i+1}=\{wv:w\in V^{i}{\text{ and }}v\in V\}}$для каждого . ${\displaystyle i>0}$

Если это формальный язык, то -я степень множества является сокращением для объединения множества с самим собой времен. То есть под ним можно понимать набор всех строк , которые можно представить как конкатенацию строк в . ${\displaystyle V}$ ${\displaystyle V^{i}}$ ${\displaystyle i}$ ${\displaystyle V}$ ${\displaystyle V}$ ${\displaystyle i}$ ${\displaystyle V^{i}}$ ${\displaystyle i}$ ${\displaystyle V}$

Определение звезды Клини : ^[2] ${\displaystyle V}$

${\displaystyle V^{*}=\bigcup _{i\geq 0}V^{i}=V^{0}\cup V^{1}\cup V^{2}\cup V^{3}\cup V^{4}\cup \cdots .}$

Это означает, что оператор звезды Клини является идемпотентным унарным оператором : для любого набора строк или символов, как и для каждого . ${\displaystyle (V^{*})^{*}=V^{*}}$ ${\displaystyle V}$ ${\displaystyle (V^{*})^{i}=V^{*}}$ ${\displaystyle i\geq 1}$

Клини плюс

В некоторых формальных языковых исследованиях (например, в теории AFL ) используется вариант операции «звезда Клини», называемый плюс Клини . В «Клин плюс» этот термин в приведенном выше союзе отсутствует. Другими словами, «Клин плюс » ${\displaystyle V^{0}}$ ${\displaystyle V}$

${\displaystyle V^{+}=\bigcup _{i\geq 1}V^{i}=V^{1}\cup V^{2}\cup V^{3}\cup \cdots ,}$

или

${\displaystyle V^{+}=V^{*}V.}$^[3]

Примеры

Пример звезды Клини, примененной к набору струн:

{"ab","c"} ^* = { ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", «abcc», «cabab», «cabc», «ccab», «ccc», ...}.

Пример использования Kleene plus к набору символов:

{"a", "b", "c"} ⁺ = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc" ", "ca", "cb", "cc", "aaa", "aab", ...}.

Звезда Клини применена к тому же набору символов:

{"a", "b", "c"} ^* = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", «bc», «ca», «cb», «cc», «aaa», «aab», ...}.

Пример звезды Клини, примененной к пустому множеству:

∅ ^* = {ε}.

Пример применения «Клин плюс» к пустому множеству:

∅ ⁺ = ∅ ∅ ^* = { } = ∅,

где конкатенация — ассоциативное и некоммутативное произведение.

Пример Клини плюс и Клини звездочка, примененных к одноэлементному набору, содержащему пустую строку:

Если , то и для каждого , следовательно . ${\displaystyle V=\{\varepsilon \}}$ ${\displaystyle V^{i}=\{\varepsilon \}}$ ${\displaystyle i}$ ${\displaystyle V^{*}=V^{+}=\{\varepsilon \}}$

Обобщение

Строки образуют моноид с конкатенацией в качестве бинарной операции и ε в качестве единичного элемента. Звезда Клини определена для любого моноида, а не только для струн. Точнее, пусть ( M , ⋅ ) — моноид и S ⊆ M. Тогда S ^* — наименьший подмоноид M , содержащий S ; то есть S ^* содержит нейтральный элемент M , множество S , и таково, что если x , y ∈ S ^* , то x ⋅ y ∈ S ^* .

Более того, звезда Клини обобщается путем включения *-операции (и объединения) в саму алгебраическую структуру посредством понятия полного звездного полукольца . ^[4]

Смотрите также

• Подстановочный знак
• Глоб (программирование)

Рекомендации

1. Наюки Минасэ (10 мая 2011 г.). «Счетные множества и звезда Клини». Проект Наюки . Проверено 11 января 2012 г.
2. Флетчер, Питер; Хойл, Хьюз; Пэтти, К. Уэйн (1991). Основы дискретной математики . Брукс/Коул. п. 656. ИСБН 0534923739. Замыкание Клини L ^* L определяется как . ${\textstyle \bigcup _{i=0}^{\infty }L^{i}}$
3. Это уравнение справедливо, потому что каждый элемент V ⁺ должен либо состоять из одного элемента V и конечного числа непустых членов V , либо быть просто элементом V (где V сам извлекается путем объединения V с ε).
4. Дросте, М.; Куич, В. (2009). «Глава 1: Полукольца и формальный степенной ряд». Справочник по взвешенным автоматам . Монографии по теоретической информатике. Спрингер. п. 9. дои : 10.1007/978-3-642-01492-5_1. ISBN 978-3-642-01491-8.

дальнейшее чтение

• Хопкрофт, Джон Э .; Уллман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Аддисон-Уэсли .