Звезда Клини

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

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

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

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

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

ОпределениеПравить

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

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

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

$V^0=\left\{\mathrm{\epsilon <!--\; \epsilon \; -->}\right\}$$V^0 = \left\{\varepsilon \right\}$ .

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

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

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

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

Звезда КлиниПравить

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

$V^{\ast <!--\; \ast \; -->}=\underset{i=0}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\bigcup <!--\; \bigcup \; -->}}{V}^i$$V^* = \bigcup_{i=0}^{\infty} V^i$ .

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

Плюс КлиниПравить

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

$V^{+}=\underset{i=1}{\overset{\mathrm{\infty <!--\; \infty \; -->}}{\bigcup <!--\; \bigcup \; -->}}{V}^i$$V^+ = \bigcup_{i=1}^{\infty} V^i$ .

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

СвойстваПравить

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

$V^{\ast <!--\; \ast \; -->}={V^{\ast <!--\; \ast \; -->}}^{\ast <!--\; \ast \; -->}$$V^* = {V^*}^*$ .

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

$V\subseteq <!--\; \subseteq \; -->V^{\ast <!--\; \ast \; -->}$$V \subseteq V^*$ .

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

$\mathrm{\epsilon <!--\; \epsilon \; -->}\in <!--\; \in \; -->V^{\ast <!--\; \ast \; -->}$$\varepsilon \in V^*$ .

• Счётность:

$\left|V^{\ast <!--\; \ast \; -->}\right|=\left|V^{+}\right|={\mathrm{\aleph <!--\; \aleph \; -->}}_0\Leftarrow <!--\; \Leftarrow \; -->\mathrm{\varnothing <!--\; \varnothing \; -->}\ne <!--\; \ne \; -->V\ne <!--\; \ne \; -->\{\mathrm{\epsilon <!--\; \epsilon \; -->}\}$$\left|V^* \right| = \left|V^+ \right| = \alef_0 \Leftarrow \varnothing \ne V \ne \{\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\{\mathrm{\epsilon <!--\; \epsilon \; -->}\right\}}^{\ast <!--\; \ast \; -->}={\left\{\mathrm{\epsilon <!--\; \epsilon \; -->}\right\}}^{+}=\left\{\mathrm{\epsilon <!--\; \epsilon \; -->}\right\}$$\left\{\varepsilon \right\}^* = \left\{\varepsilon \right\}^+ = \left\{\varepsilon \right\}$ .

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

${\mathrm{\varnothing <!--\; \varnothing \; -->}}^{\ast <!--\; \ast \; -->}=\left\{\mathrm{\epsilon <!--\; \epsilon \; -->}\right\}$$\varnothing^* = \left\{\varepsilon \right\}$ .

${\mathrm{\varnothing <!--\; \varnothing \; -->}}^{+}={\mathrm{\varnothing <!--\; \varnothing \; -->}}^{\ast <!--\; \ast \; -->}\mathrm{\varnothing <!--\; \varnothing \; -->}=\mathrm{\varnothing <!--\; \varnothing \; -->}$$\varnothing^+ = \varnothing^* \varnothing = \varnothing$ .

ОбобщениеПравить

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