Клини звезда
В математической логике и информатике звезда Клини (или оператор Клини , или замыкание Клини — это унарная операция , выполняемая либо над наборами строк ) , либо над наборами символов или символов. В математике,она более известна как конструкция свободного моноида . Применение звезды Клини к набору написано как . Он широко используется для регулярных выражений , в контексте которого он был введен Стивеном Клини для характеристики определенных автоматов , где он означает «ноль или более повторений».
- Если представляет собой набор строк, то определяется как надмножество наименьшее который содержит пустую строку и закрывается при операции конкатенации строк .
- Если представляет собой набор символов или знаков, то — это набор всех строк над символами в , включая пустую строку .
Набор также может быть описан как набор, содержащий пустую строку и все строки конечной длины, которые могут быть сгенерированы путем объединения произвольных элементов , что позволяет использовать один и тот же элемент несколько раз. Если является либо пустым множеством ∅, либо одноэлементным множеством , затем ; если любое другое конечное или счетно бесконечное множество , то является счетным бесконечным множеством. [1] Как следствие, каждый формальный язык в конечном или счетно бесконечном алфавите счетно, так как является подмножеством счетно бесконечного множества .
Операторы используются в правилах перезаписи порождающих грамматик .
Определение и обозначения [ править ]
Учитывая набор ,определять
- (язык, состоящий только из пустой строки),
- ,
и рекурсивно определим множество
- для каждого .
Если является формальным языком, то , -я степень множества , является сокращением для объединения множества с самим собой раз. То есть, можно понимать как набор всех строк , которые можно представить как конкатенацию струны в .
Определение звезды Клини на является [2]
Это означает, что звездный оператор Клини является идемпотентным унарным оператором : для любого набора строк или символов, например для каждого .
Клини плюс [ править ]
В некоторых формальных языковых исследованиях (например, в теории AFL вариант операции «звезда Клини», называемый плюс Клини ) используется . В Kleene plus отсутствует термин в вышеуказанном союзе. Другими словами, «Клин плюс» является
или
Примеры [ править ]
Пример звезды Клини, примененной к набору струн:
- {"аб","с"} * = { ε, "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" ", "ааа", "ааб", ...}.
Пример звезды Клини, примененной к пустому множеству:
- ∅ * = {е}.
Пример применения «Клин плюс» к пустому множеству:
- ∅ + = ∅ ∅ * = { } = ∅,
где конкатенация — ассоциативное и некоммутативное произведение.
Пример Клини плюс и Клини звездочка, примененных к одноэлементному набору, содержащему пустую строку:
- Если , тогда также для каждого , следовательно .
Обобщение [ править ]
Строки образуют моноид с конкатенацией в качестве бинарной операции и ε в качестве единичного элемента. Звезда Клини определена для любого моноида, а не только для струн.Точнее, пусть ( M — моноид и S ⊆ M. , ⋅ ) Тогда С * — наименьший субмоноид M , содержащий S ; то есть С * содержит нейтральный элемент M , множество S , и таков, что если x , y ∈ S * , то x ⋅ y ∈ S * .
Более того, звезда Клини обобщается путем включения *-операции (и объединения) в саму алгебраическую структуру посредством понятия полного звездного полукольца . [4]
См. также [ править ]
Ссылки [ править ]
- ^ Наюки Минасэ (10 мая 2011 г.). «Счетные множества и Клини Стар » Проект Наюки Получено 11 января.
- ^ Флетчер, Питер; Хойл, Хьюз; Пэтти, К. Уэйн (1991). Основы дискретной математики . Брукс/Коул. п. 656. ИСБН 0534923739 .
Закрытие Клини L * L как определяется .
- ^ Это уравнение справедливо, потому что каждый элемент 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-е изд.). Аддисон-Уэсли .