Звезда Клини

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

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

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

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

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

Определение

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

$i$-я степень множества $V$ — это конкатенация множества $V$ с самим собой $i-1$ раз.

Нулевая степень любого множества неизменна:

$V^{0}=\left\{\varepsilon \right\}$.

Остальные степени определяются рекурсивно:

$V^{i}=V^{i-1}V=\left\{wv\left|\,w\in V^{i-1}\land v\in V\right.\right\}$, где $i\in \mathbb {N}$.

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

то $V^{i}$ — множество строк длиной $i$ символов, взятых из $V$.

Звезда Клини

Замыкание Клини множества $V$ есть

$V^{*}=\bigcup _{i=0}^{\infty }V^{i}$.

То есть это множество всех строк конечной длины́, порождённое элементами множества $V$.

Плюс Клини

Есть операция, аналогичная звезде Клини, — плюс Клини:

$V^{+}=\bigcup _{i=1}^{\infty }V^{i}$.

Как видим, отличается тем, что пропущено $V^{0}$, содержащее пустую строку.

Свойства

• Связь операций:
  1. $V^{+}=V^{*}V$
  2. $V^{+}=V^{*}\Leftrightarrow \varepsilon \in V$
• Идемпотентность:

$V^{*}={V^{*}}^{*}$.

• Замыкание Клини включает в себя порождающее множество:

$V\subseteq V^{*}$.

• Замыкание Клини всегда содержит пустую строку:

$\varepsilon \in V^{*}$.

• Счётность:

$\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", …}.

Для множества из пустой строки

$\left\{\varepsilon \right\}^{*}=\left\{\varepsilon \right\}^{+}=\left\{\varepsilon \right\}$.

Для пустого множества

$\varnothing ^{*}=\left\{\varepsilon \right\}$.

$\varnothing ^{+}=\varnothing ^{*}\varnothing =\varnothing$.

Обобщение

Стро́ки образуют моноид по конкатенации с нейтральным элементом $\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.