Звезда Клини

Материал из Seo Wiki - Поисковая Оптимизация и Программирование

Перейти к: навигация, поиск

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

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

Содержание

Определение

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

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

<math>

V^0 = \left\{\epsilon \right\} </math>. Остальные степени определяются рекурсивно:

<math>

V^{i+1} = V^i V = \left\{wv \left| w \in V^i \land v \in V \right.\right\} </math>, где <math> i \in \N_0 </math>.

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

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

Звезда Клини

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

<math>

V^* = \bigcup_{i=0}^{\infty} V^i </math>.

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

Плюс Клини

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

<math>

V^+ = \bigcup_{i=1}^{\infty} V^i </math>. Как видим, отличается тем, что пропущено <math> V^0 </math>, содержащее пустую строку.

Свойства

<math> V^* = {V^*}^* </math>.
  • Замыкание Клини включает в себя порождающее множество:
<math> V \subseteq V^* </math>.
  • Замыкание Клини всегда содержит пустую строку:
<math> \epsilon \in V^* </math>.
<math>

\left|V^* \right| = \left|V^+ \right| = \alef_0 \Leftarrow \varnothing \not= V \not= \left\{\epsilon \right\} </math>.

Примеры

Для множества строк
{"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", …}.
Для множества из пустой строки
<math>

\left\{\epsilon \right\}^* = \left\{\epsilon \right\}^+ = \left\{\epsilon \right\} </math>.

Для пустого множества
<math> \varnothing^* = \left\{\epsilon \right\} </math>.
<math> \varnothing^+ = \varnothing^* \varnothing = \varnothing </math>.

Обобщение

Стро́ки образуют моноид по конкатенации с нейтральным элементом <math> \epsilon </math>. Таким образом, определение звезды́ Клини можно распространить на любой моноид.

Литература

  • 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

См. также

ca:Clausura de Kleene de:Kleenesche und positive Hülle el:Αστέρι Κλέινι en:Kleene star es:Clausura de Kleene fa:ستاره کلین fi:Kleenen tähti fr:Fermeture de Kleene hr:Kleeneov operator it:Star di Kleene ja:クリーネ閉包 nl:Kleene-ster pl:Domknięcie Kleene'ego pt:Fecho de Kleene ro:Închidere Kleene sr:Клинијево затворење zh:克莱尼星号

Личные инструменты

Served in 0.107 secs.