Звезда́ Кли́ни (или замыка́ние Кли́ни ) в математической логике и информатике — унарная операция над множеством строк либо символов . Замыкание Клини множества V обозначается V *. Широко применяется в регулярных выражениях .

Если V — множество строк

то V * — минимальное надмножество множества V , которое содержит ε ( пустую строку ) и замкнуто относительно конкатенации . Это также множество всех строк, полученных конкатенацией нуля или более строк из V .

Если V — множество символов

то V * — множество всех строк из символов из V с добавлением пустой строки.

Определение

Степень множества

${\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}}$ , содержащее пустую строку.

Свойства

• Связь операций:
  1. ${\displaystyle V^{+}=V^{*}V}$
  2. ${\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 .
• Katrin Erk, Lutz Priese. Theoretische Informatik: eine umfassende Einführung. — 2., erw. — Springer-Verlag, 2002. — С. 27—29. — ISBN 3-540-42624-8 .