Звезда Клини

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

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

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

Определение

[править | править код]

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

[править | править код]

-я степень множества — это конкатенация множества с самим собой раз.

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

.

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

, где .
Если  — множество символов
то  — множество строк длиной символов, взятых из .

Звезда Клини

[править | править код]

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

.

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

Плюс Клини

[править | править код]

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

.

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

  • Связь операций:
  • Идемпотентность:
.
  • Замыкание Клини включает в себя порождающее множество:
.
  • Замыкание Клини всегда содержит пустую строку:
.
.
Для множества строк
{"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", …}.
Для множества из пустой строки
.
Для пустого множества
.
.

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

Литература

[править | править код]
  • 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.