Звезда Клини

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

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

Определение

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

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

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

.

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

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

Звезда Клини

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

.

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

Плюс Клини

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

.

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

Свойства

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

Примеры

Для множества строк
{"Go", "Ukraine"}* = {ε, "Go", "Ukraine", "GoGo", "GoUkraine", "UkraineGo", "UkraineUkraine", "GoGoGo", "GoGoUkraine", "GoUkraineGo", …}.
Для множества символов
{'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.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.