звезда Клини

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

В математической логике и информатике звезда Клини (или оператор Клини или замыкание Клини ) — это унарная операция , либо над наборами строк , либо над наборами символов или символов. В математике она более известна как свободная моноидная конструкция. Применение звезды Клини к набору записывается как . Она широко используется для регулярных выражений , что является контекстом, в котором она была введена Стивеном Клини для характеристики определенных автоматов , где она означает «ноль или более повторений». ${\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», ...}.

Пример применения знака «Клин плюс» к набору символов:

{"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», ...}.

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

∅ ^* = {ε}.

Пример применения Kleene plus к пустому множеству:

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

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

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

Если , то также для каждого , следовательно . ${\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. ISBN 0534923739Замыкание Клини L ^* для L определяется как . ${\textstyle \bigcup _{i=0}^{\infty }L^{i}}$
3. Это уравнение справедливо, поскольку каждый элемент V ⁺ должен либо состоять из одного элемента V и конечного числа непустых членов в V , либо быть просто элементом V (где само V получается путем объединения V с ε).
4. Droste, M.; Kuich, W. (2009). "Глава 1: Полукольца и формальные степенные ряды". Handbook of Weighted Automata . Monographs in Theoretical Computer Science. Springer. p. 9. doi :10.1007/978-3-642-01492-5_1. ISBN 978-3-642-01491-8.

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

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