Введение

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

В математической логике и информатике звезда Клине (или оператор Клине, или замыкание Клине) — это унарная операция, применяемая либо к множествам строк, либо к множествам символов или знаков. В математике она чаще известна как построение свободного моноида. Применение звезды Клине к множеству записывается как . Она широко используется в регулярных выражениях, в контексте которых она была введена Стивеном Клине для описания определенных автоматов, где она означает «ноль или более повторений». Если — множество строк, то определяется как наименьшее надмножество , содержащее пустую строку и замкнутое относительно операции конкатенации строк. Если — множество символов или знаков, то — это множество всех строк, составленных из символов из , включая пустую строку.

Множество также можно описать как множество, содержащее пустую строку и все строки конечной длины, которые могут быть сгенерированы конкатенацией произвольных элементов , допускающей многократное использование одного и того же элемента. Если является либо пустым множеством ∅, либо одноэлементным множеством { }, то ; если — любое другое конечное или счетно бесконечное множество, то — счетно бесконечное множество. Как следствие, каждый формальный язык над конечным или счетно бесконечным алфавитом счётен, поскольку он является подмножеством счётного бесконечного множества .

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

Обобщение

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