Русская Википедия:Звезда Клини
Звезда́ Кли́ни (или замыка́ние Кли́ни) в математической логике и информатике — унарная операция над множеством строк либо символов. Замыкание Клини множества V обозначается V*. Широко применяется в регулярных выражениях.
- Если V — множество строк
- то V* — минимальное надмножество множества V, которое содержит ε (пустую строку) и замкнуто относительно конкатенации. Это также множество всех строк, полученных конкатенацией нуля или более строк из V.
- Если V — множество символов
- то V* — множество всех строк из символов из V с добавлением пустой строки.
Определение
Степень множества
<math>i </math>-я степень множества <math>V</math> — это конкатенация множества <math>V</math> с самим собой <math>i-1</math> раз.
Нулевая степень любого множества неизменна:
- <math> V^0 = \left\{\varepsilon \right\} </math>.
Остальные степени определяются рекурсивно:
- <math> V^i = V^{i-1} V = \left\{wv \left|\, w \in V^{i-1} \land v \in V \right. \right\} </math>, где <math>i \in \N</math>.
- Если <math>V</math> — множество символов
- то <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^*V </math>
- <math> V^+ = V^* \Leftrightarrow \varepsilon \in V</math>
- Идемпотентность:
- <math> V^* = {V^*}^* </math>.
- Замыкание Клини включает в себя порождающее множество:
- <math> V \subseteq V^* </math>.
- Замыкание Клини всегда содержит пустую строку:
- <math> \varepsilon \in V^* </math>.
- <math>
\left|V^* \right| = \left|V^+ \right| = \alef_0 \Leftarrow \varnothing \ne V \ne \{\varepsilon\} </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\{\varepsilon \right\}^* = \left\{\varepsilon \right\}^+ = \left\{\varepsilon \right\} </math>.
- Для пустого множества
- <math> \varnothing^* = \left\{\varepsilon \right\} </math>.
- <math> \varnothing^+ = \varnothing^* \varnothing = \varnothing </math>.
Обобщение
Стро́ки образуют моноид по конкатенации с нейтральным элементом <math>\varepsilon</math>. Таким образом, определение звезды́ Клини можно распространить на любой моноид.
См. также
- Алгебра Клини
- Регулярные выражения
- Расширенная Бэкус — Наурова форма
- Лемма о разрастании
- Стивен Клини
Литература
