В математичній логіці та інформатиці, зірка Кліні (або оператор Кліні, або замикання Кліні) це унарна операція, або на множинах рядків або на множинах символів або букв. Застосування зірки Кліні до множини V записується як V*. Це широко використовується в регулярних виразах, в контексті яких вони були введені Стівеном Кліні для описання деяких автоматів.
- Якщо V це набір рядків, тоді V* визначається як найменша надмножина V, яка містить λ (порожній рядок) і є замиканням для операції конкатенації рядків. Ця множина також може бути описана як множина рядків, які можуть бути утворені конкатенацією нуля або більшої кількістю рядків з V.
- Якщо V це набір символів або букв, тоді V* це множина всіх рядків над символами з V, включно з порожнім рядком.
Визначення і запис
Дано
рекурсивно визначимо множину
де
Якщо — формальна мова, тоді
, 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 містить порожнє слово.
Узагальнення
Рядки утворюють моноїд з конкатенацією як бінарною операцією і нейтральним елементом λ. Зірка Кліні визначена для будь-якого моноїда, не тільки рядків. Більш точно, нехай це моноїд, і
. Тоді
— найменший моноїд
, що містить
; такий, що
містить нейтральний елемент з
, множину
, і такий, що якщо
, тоді
.
Див. також
Примітки
- . Архів оригіналу за 29 травня 2015. Процитовано 29 травня 2015.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет