Звезда Клини

редактировать

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

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

Набор V также можно описать как набор строк конечной длины, которые могут быть сгенерированы путем объединения произвольных элементов V, что позволяет использовать один и тот же элемент несколько раз. Если V является либо пустым набором ∅, либо одноэлементным набором {ε}, то V = {ε}; если V - любое другое конечное множество или счетно бесконечное множество, то V - счетно бесконечное множество. Как следствие, каждый формальный язык над конечным или счетно-бесконечным алфавитом является счетным.

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

Содержание

1 Определение и обозначение
2 Kleene plus
3 Примеры
4 Обобщение
5 См. Также
6 Ссылки
7 Дополнительная литература

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

Для данного набора V определить

V = {ε} (язык, состоящий только из пустая строка),

V = V

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

V = {wv: w ∈ V и v ∈ V} для каждого i>0.

Если V является формального языка, тогда V, i-я степень множества V, является сокращением для конкатенации множества V с самим собой i раз. То есть, V можно понимать как набор всех строк, которые могут быть представлены как конкатенация i строк в V.

Определение звезды Клини на V:

V ∗ = ⋃ i ≥ 0 V i = V 0 ∪ V 1 ∪ V 2 ∪ V 3 ∪ V 4 ∪ ⋯. {\ 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 ^ {*} = \ bigcup _ {я \ geq 0} V ^ {i} = V ^ {0} \ cup V ^ {1} \ cup V ^ {2} \ cup V ^ {3} \ чашка V ^ {4} \ чашка \ cdots.}

Обратите внимание, что звездный оператор Клини является идемпотентным унарным оператором: (V) = V для любого набора V строк или символов.

Клини плюс

В некоторых исследованиях формального языка (например, теория AFL ) используется вариант звездной операции Клини, называемый Клини плюс. Клини плюс пропускает член V в приведенном выше союзе. Другими словами, Клини плюс на V равен

V + = ⋃ i ≥ 1 V i = V 1 ∪ V 2 ∪ V 3 ∪ ⋯. {\ displaystyle V ^ {+} = \ bigcup _ {i \ geq 1} V ^ {i} = V ^ {1} \ cup V ^ {2} \ cup V ^ {3} \ cup \ cdots.}

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

Для каждого множества L Клини плюс L (обозначенный L) равен конкатенации L и L; это верно, потому что каждый элемент L должен быть либо составлен из одного элемента L и конечного числа непустых членов в L, либо является просто элементом L (где сам L извлекается путем объединения L с ε). И наоборот, L = {ε} ∪ L.

Примеры

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

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

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

∅ = {ε}.

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

∅ = ∅ ∅ = {} = ∅,

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

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

Если V = {ε}, то также V = {ε} для каждого i, следовательно, V = V = { ε}.

Обобщение

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

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

См. также

Ссылки

Дополнительная литература

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