Меню Главная Случайная статья Настройки Звезда Клини Материал из https://ru.wikipedia.org Звезда Клини (или замыкание Клини) в математической логике и информатике — унарная операция над множеством строк либо символов. Замыкание Клини множества V обозначается V*. Широко применяется в регулярных выражениях. Если V — множество строк то V* — минимальное надмножество множества V, которое содержит (пустую строку) и замкнуто относительно конкатенации. Это также множество всех строк, полученных конкатенацией нуля или более строк из V. Если V — множество символов то V* — множество всех строк из символов из V с добавлением пустой строки. Содержание 1 Определение 1.1 Степень множества 1.2 Звезда Клини 1.3 Плюс Клини 2 Свойства 3 Примеры 4 Обобщение 5 См. также 6 Литература Определение Степень множества ${\displaystyle i}$-я степень множества ${\displaystyle V}$ — это конкатенация множества ${\displaystyle V}$ с самим собой ${\displaystyle i-1}$ раз. Нулевая степень любого множества неизменна: ${\displaystyle V^{0}=\left\{\varepsilon \right\}}$. Остальные степени определяются рекурсивно: ${\displaystyle V^{i}=V^{i-1}V=\left\{wv\left|\,w\in V^{i-1}\land v\in V\right.\right\}}$, где ${\displaystyle i\in \mathbb {N} }$. Если ${\displaystyle V}$ — множество символов то ${\displaystyle V^{i}}$ — множество строк длиной ${\displaystyle i}$ символов, взятых из ${\displaystyle V}$. Звезда Клини Замыкание Клини множества ${\displaystyle V}$ есть ${\displaystyle V^{*}=\bigcup _{i=0}^{\infty }V^{i}}$. То есть это множество всех строк конечной длины, порождённое элементами множества ${\displaystyle V}$. Плюс Клини Есть операция, аналогичная звезде Клини, — плюс Клини: ${\displaystyle V^{+}=\bigcup _{i=1}^{\infty }V^{i}}$. Как видим, отличается тем, что пропущено ${\displaystyle V^{0}}$, содержащее пустую строку. Свойства Связь операций: ${\displaystyle V^{+}=V^{*}V}$ ${\displaystyle V^{+}=V^{*}\Leftrightarrow \varepsilon \in V}$ Идемпотентность: ${\displaystyle V^{*}={V^{*}}^{*}}$. Замыкание Клини включает в себя порождающее множество: ${\displaystyle V\subseteq V^{*}}$. Замыкание Клини всегда содержит пустую строку: ${\displaystyle \varepsilon \in V^{*}}$. Счётность: ${\displaystyle \left|V^{*}\right|=\left|V^{+}\right|=\aleph _{0}\Leftarrow \varnothing \neq V\neq \{\varepsilon \}}$. Примеры Для множества строк {"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", …}. Для множества из пустой строки ${\displaystyle \left\{\varepsilon \right\}^{*}=\left\{\varepsilon \right\}^{+}=\left\{\varepsilon \right\}}$. Для пустого множества ${\displaystyle \varnothing ^{*}=\left\{\varepsilon \right\}}$. ${\displaystyle \varnothing ^{+}=\varnothing ^{*}\varnothing =\varnothing }$. Обобщение Строки образуют моноид по конкатенации с нейтральным элементом ${\displaystyle \varepsilon }$. Таким образом, определение звезды Клини можно распространить на любой моноид. См. также Алгебра Клини Регулярные выражения Расширенная Бэкус — Наурова форма Лемма о разрастании Стивен Клини Литература John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman. Introduction to Automata Theory, Languages, and Computation. — 3rd Edition. — 2006. — 535 p. — ISBN 0321462254.