Звезда Клини

Звезда́ Кли́ни (или замыка́ние Кли́ни) в математической логике и информатике — унарная операция над множеством строк либо символов. Замыкание Клини множества 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", "Ukraine"}* = {ε, "Go", "Ukraine", "GoGo", "GoUkraine", "UkraineGo", "UkraineUkraine", "GoGoGo", "GoGoUkraine", "GoUkraineGo", …}.
Для множества символов: {'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.

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.