Звезда Клини
Звезда́ Кли́ни (или замыка́ние Кли́ни) в математической логике и информатике — унарная операция над множеством строк либо символов. Замыкание Клини множества 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", …}.
- Для множества из пустой строки
- .
- Для пустого множества
- .
- .
Обобщение
[править | править код]Стро́ки образуют моноид по конкатенации с нейтральным элементом . Таким образом, определение звезды́ Клини можно распространить на любой моноид.
См. также
[править | править код]- Алгебра Клини
- Регулярные выражения
- Расширенная Бэкус — Наурова форма
- Лемма о разрастании
- Стивен Клини
Литература
[править | править код]- John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. — 3rd Edition. — 2006. — 535 p. — ISBN 0321462254.
- Katrin Erk, Lutz Priese. Theoretische Informatik: eine umfassende Einführung. — 2., erw. — Springer-Verlag, 2002. — С. 27—29. — ISBN 3-540-42624-8.