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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

Визначення і запис[ред.ред. код]

Дано

 V_0=\{\lambda\}\,

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

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

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

Визначенням зірки Кліні на V є  V^*=\bigcup_{i \in \N}V_i = \left \{\lambda \right\} \cup V_1 \cup V_2 \cup V_3 \cup \ldots.

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

В деяких дослідженнях формальних мовах, використовується різновид опреції Кліні званий плюс Кліні. Плюс Кліні упускає терм V_0 в попередньому об'єднанні. Іншими словами, плюс V це  V^+=\bigcup_{i \in \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", ...}.

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

\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^*.