Открыть главное меню

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

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

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

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

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

 .

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

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

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

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

 .

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

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

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

 .

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

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

  • Связь операций:
    1.  
    2.  
  • Идемпотентность:
 .
  • Замыкание Клини включает в себя порождающее множество:
 .
  • Замыкание Клини всегда содержит пустую строку:
 .
 .

ПримерыПравить

Для множества строк
{"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.