Звезда́ Кли́ни (или замыка́ние Кли́ни) в математической логике и информатике — унарная операция над множеством строк либо символов. Замыкание Клини множества V обозначается V*. Широко применяется в регулярных выражениях.
Если V — множество строк то V* — минимальное надмножество множества V, которое содержит ε (пустую строку) и замкнуто относительно конкатенации. Это также множество всех строк, полученных конкатенацией нуля или более строк из V. Если V — множество символов то V* — множество всех строк из символов из V с добавлением пустой строки.
Определение
Степень множества -я степень множества — это конкатенация множества с самим собой раз.
Нулевая степень любого множества неизменна: . Остальные степени определяются рекурсивно: , где .
Если — множество символов то — множество строк длиной символов, взятых из .
Звезда Клини Замыкание Клини множества есть .
То есть это множество всех строк конечной длины́, порождённое элементами множества .
Плюс Клини Есть операция, аналогичная звезде Клини, — плюс Клини: . Как видим, отличается тем, что пропущено , содержащее пустую строку.
Свойства Связь операций:
Идемпотентность: . Замыкание Клини включает в себя порождающее множество: . Замыкание Клини всегда содержит пустую строку: . Счётность: .
Примеры Для множества строк {"Go", "Russia"}* = {ε, "Go", "Russia", "GoGo", "GoRussia", "RussiaGo", "RussiaRussia", "GoGoGo", "GoGoRussia", "GoRussiaGo", …}. Для множества символов {'a', 'b', 'c'}* = {ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", "aaa", …}. Для множества из пустой строки . Для пустого множества . .
Обобщение Стро́ки образуют моноид по конкатенации с нейтральным элементом . Таким образом, определение звезды́ Клини можно распространить на любой моноид.
См. также Алгебра Клини Регулярные выражения Расширенная Бэкус — Наурова форма Лемма о разрастании Стивен Клини
Литература
Категория:Формальные языки Категория:Математические знаки