Звезда Клини

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

Определение[править | править вики-текст]

Степень множества[править | править вики-текст]

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

 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 \N.
Если V — множество символов
то V^i — множество строк длиной i символов, взятых из V.

Звезда Клини[править | править вики-текст]

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

 
V^* = \bigcup_{i=0}^{\infty} V^i .

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

Плюс Клини[править | править вики-текст]

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


V^+ = \bigcup_{i=1}^{\infty} V^i .

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

Свойства[править | править вики-текст]

 V^* = {V^*}^* .
  • Замыкание Клини включает в себя порождающее множество:
 V \subseteq V^* .
  • Замыкание Клини всегда содержит пустую строку:
 \varepsilon \in V^* .
 
\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\{\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

См. также[править | править вики-текст]