Определение
Звезда Клини
Замыкание Клини множества
есть
-
.
То есть это множество всех строк конечной длины́, порождённое элементами множества
.
Плюс Клини
Есть операция, аналогичная звезде Клини, — плюс Клини:
-
.
Как видим, отличается тем, что пропущено
, содержащее пустую строку.
Свойства
- Связь операций:
-
-
- Идемпотентность:
-
.
- Замыкание Клини включает в себя порождающее множество:
-
.
- Замыкание Клини всегда содержит пустую строку:
-
.
-
.
Примеры
- Для множества строк
- {"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.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .