Зірочка Кліні

В математичній логіці та інформатиці, зірка Кліні (або оператор Кліні, або замикання Кліні) це унарна операція, або на множинах рядків або на множинах символів або букв. Застосування зірки Кліні до множини V записується як V*. Це широко використовується в регулярних виразах, в контексті яких вони були введені Стівеном Кліні для описання деяких автоматів.

1. Якщо V це набір рядків, тоді V* визначається як найменша надмножина V, яка містить λ (порожній рядок) і є замиканням для операції конкатенації рядків. Ця множина також може бути описана як множина рядків, які можуть бути утворені конкатенацією нуля або більшої кількістю рядків з V.
2. Якщо V це набір символів або букв, тоді V* це множина всіх рядків над символами з V, включно з порожнім рядком.

Визначення і запис

Дано

$V_0=\{\lambda \}$

рекурсивно визначимо множину

$V_{i+1}=\{wv\mid w\in V_i\text{ and }v\in V\}$ де $i\ge 0.$

Якщо $V$ — формальна мова, тоді $V_i$, i-й ступінь множини $V$, це умовний запис для конкатенації множин $V$ із собою i разів. Тобто, $V_i$ можна розуміти як множину всіх рядків, що можуть бути представлені як конкатенація i рядків з $V$.

Визначенням зірки Кліні на $V$ є $V^{*}=\bigcup _{i\in \mathbb{N}}{V}_i=\left\{\lambda \right\}\cup V_1\cup V_2\cup V_3\cup \dots .$

Тобто, це набір всіх можливих рядків скінченної довжини утворених з символів з $V$.

В деяких дослідженнях формальних мов, використовується різновид операції Кліні званий плюс Кліні. Плюс Кліні упускаєШаблон:Уточнити терм $V_0$ в попередньому об'єднанні. Іншими словами, плюс $V$ це $V^{+}=\bigcup _{i\in \mathbb{N}\setminus \{0\}}{V}_i=V_1\cup V_2\cup V_3\cup \dots .$

Додатково, зірка Кліні використовується в теорії оптимальності.

Приклади

Приклад зірки Кліні застосованої до множини рядків:

{"ab", "c"}* = {λ, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc", "ccab", "ccc", ...}.

Приклад зірки Кліні застосованої до множини букв:

{'a', 'b', 'c'}* = {λ, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", ...}.

Приклад зірки Кліні застосованої до порожньої множини:

${\varnothing }^{*}=\{\lambda \}.$

Приклад плюса Кліні застосованого до порожньої множини:

${\varnothing }^{+}=\varnothing {\varnothing }^{*}=\{\}=\varnothing .$

Зауважимо, що для кожної множини L, $L^{+}$ дорівнює конкатенації L з $L^{*}$. І навпаки, $L^{*}$ можна записати як $\{\lambda \}\cup L^{+}$. Оператори $L^{+}$ і $L^{*}$ описують одну множину тоді і тільки тоді, якщо множина L містить порожнє слово.

Узагальнення

Рядки утворюють моноїд з конкатенацією як бінарною операцією і нейтральним елементом λ. Зірка Кліні визначена для будь-якого моноїда, не тільки рядків. Більш точно, нехай $(M,\cdot )$ це моноїд, і $S\subseteq M$. Тоді $S^{*}$ — найменший моноїд $M$, що містить $S$ ; такий, що $S^{*}$ містить нейтральний елемент з $M$, множину $S$, і такий, що якщо $x,y\in S^{*}$, тоді $x\cdot y\in S^{*}$.

Див. також

• Висота ітерації мови