Звезда Клини

Звезда́ Кли́ни (или замыка́ние Кли́ни) в математической логике и информатике — унарная операция над множеством строк либо символов. Замыкание Клини множества 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 \}

.

Для множества строк

Пусть дано множество строк {«Да», «Нет»}.

Тогда замыкание Клини этого множества имеет вид:

{«Да», «Нет»}* = {ε, «Да», «Нет», «ДаДа», «ДаНет», «НетДа», «НетНет», «ДаДаДа», «ДаДаНет», «ДаНетДа», …}.

Для множества символов

{‘а’, ‘б’, ‘в’}* = {ε, «а», «б», «в», «аа», «аб», «ав», «ба», «бб», «бв», «ва», «вб», «вв», «ааа», …}.

Для множества из пустой строки: $\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.

Звезда Клини

Определение

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

Звезда Клини

Плюс Клини

Свойства

Примеры

Обобщение

Литература

Категории