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

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

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

Дано

${\displaystyle V_{0}=\{\lambda \}\,}$

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

${\displaystyle V_{i+1}=\{wv\mid w\in V_{i}{\mbox{ and }}v\in V\}\,}$ де ${\displaystyle i\geq 0\,.}$

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

Визначенням зірки Кліні на ${\displaystyle V}$ є ${\displaystyle V^{*}=\bigcup _{i\in \mathbb {N} }V_{i}=\left\{\lambda \right\}\cup V_{1}\cup V_{2}\cup V_{3}\cup \ldots .}$

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

В деяких дослідженнях формальних мов, використовується різновид операції Кліні званий плюс Кліні. Плюс Кліні упускає^{[уточнити]} терм ${\displaystyle V_{0}}$ в попередньому об'єднанні. Іншими словами, плюс ${\displaystyle V}$ це ${\displaystyle V^{+}=\bigcup _{i\in \mathbb {N} \setminus \{0\}}\!\!\!\!V_{i}=V_{1}\cup V_{2}\cup V_{3}\cup \ldots .}$

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

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

{"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", ...}.

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

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

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

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

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

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

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