Клини звезда

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

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

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

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

Определение и обозначения [ править ]

Учитывая набор $V$ , определять

V^{0}=\{\varepsilon \}

(язык, состоящий только из пустой строки),

V^{1}=V

,

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

V^{i+1}=\{wv:w\in V^{i}{\text{ and }}v\in V\}

для каждого

i>0

.

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

Определение звезды Клини на $V$ является ^[2]

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

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

Клини плюс [ править ]

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

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

или

V^{+}=V^{*}V.

^[3]

Примеры [ править ]

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

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

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

{"а", "б", "в"} ⁺ = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", «ааа», «ааб», ...}.

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

{"а", "б", "в"} ^* = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc" ", "ааа", "ааб", ...}.

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

∅ ^* = {е}.

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

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

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

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

Если

V=\{\varepsilon \}

, тогда также

V^{i}=\{\varepsilon \}

для каждого

i

, следовательно

V^{*}=V^{+}=\{\varepsilon \}

.

Обобщение [ править ]

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

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

См. также [ править ]

Ссылки [ править ]

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

Дальнейшее чтение [ править ]

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

[1] Наюки Минасэ (10 мая 2011 г.). «Счетные множества и Клини Стар » Проект Наюки Получено 11 января.

[2] Флетчер, Питер; Хойл, Хьюз; Пэтти, К. Уэйн (1991). Основы дискретной математики . Брукс/Коул. п. 656. ИСБН 0534923739 . Клини Закрытие L ^* L определяется как ${\textstyle \bigcup _{i=0}^{\infty }L^{i}}$ .

[3] Это уравнение справедливо, потому что каждый элемент V ⁺ должен либо состоять из одного элемента V и конечного числа непустых термов V , либо быть просто элементом V (где V сам извлекается путем объединения V с ε).

[droste-4] Дросте, М.; Куич, В. (2009). «Глава 1: Полукольца и формальный степенной ряд». Справочник по взвешенным автоматам . Монографии по теоретической информатике. Спрингер. п. 9 . дои : 10.1007/978-3-642-01492-5_1 . ISBN 978-3-642-01491-8 .

[1]

[2]

[3]

[4]