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

(Перенаправлено з Зірка Кліні)

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

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

Визначення і записРедагувати

Дано

 

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

  де  

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

Визначенням зірки Кліні на   є  

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

В деяких дослідженнях формальних мов, використовується різновид операції Кліні званий плюс Кліні. Плюс Кліні упускає[уточнити] терм   в попередньому об'єднанні. Іншими словами, плюс   це  

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

ПрикладиРедагувати

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

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

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

 

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

 

Зауважимо, що для кожної множини L,   дорівнює конкатенації L з  . І навпаки,   можна записати як  . Оператори   і   описують одну множину тоді і тільки тоді, якщо множина L містить порожнє слово.

УзагальненняРедагувати

Рядки утворюють моноїд з конкатенацією як бінарною операцією і нейтральним елементом λ. Зірка Кліні визначена для будь-якого моноїда, не тільки рядків. Більш точно, нехай   це моноїд, і  . Тоді   — найменший моноїд  , що містить   ; такий, що   містить нейтральний елемент з  , множину  , і такий, що якщо  , тоді  .

ПриміткиРедагувати