www.wikidata.uk-ua.nina.az

Зірочка Кліні В математичній логіці та інформатиці зірка Кліні або оператор Кліні або замикання Кліні це унарна операція

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

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

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

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

Дано

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Див. також Редагувати

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

  1. . Архів оригіналу за 29 травня 2015. Процитовано 29 травня 2015. 
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри
Дата публікації:
V matematichnij logici ta informatici zirka Klini abo operator Klini abo zamikannya Klini ce unarna operaciya abo na mnozhinah ryadkiv abo na mnozhinah simvoliv abo bukv Zastosuvannya zirki Klini do mnozhini V zapisuyetsya yak V Ce shiroko vikoristovuyetsya v regulyarnih virazah v konteksti yakih voni buli vvedeni Stivenom Klini dlya opisannya deyakih avtomativ Yaksho V ce nabir ryadkiv todi V viznachayetsya yak najmensha nadmnozhina V yaka mistit l porozhnij ryadok i ye zamikannyam dlya operaciyi konkatenaciyi ryadkiv Cya mnozhina takozh mozhe buti opisana yak mnozhina ryadkiv yaki mozhut buti utvoreni konkatenaciyeyu nulya abo bilshoyi kilkistyu ryadkiv z V Yaksho V ce nabir simvoliv abo bukv todi V ce mnozhina vsih ryadkiv nad simvolami z V vklyuchno z porozhnim ryadkom 1 Zmist 1 Viznachennya i zapis 2 Prikladi 3 Uzagalnennya 4 Div takozh 5 PrimitkiViznachennya i zapis RedaguvatiDano V 0 l displaystyle V 0 lambda nbsp rekursivno viznachimo mnozhinu V i 1 w v w V i and v V displaystyle V i 1 wv mid w in V i mbox and v in V nbsp de i 0 displaystyle i geq 0 nbsp Yaksho V displaystyle V nbsp formalna mova todi V i displaystyle V i nbsp i j stupin mnozhini V displaystyle V nbsp ce umovnij zapis dlya konkatenaciyi mnozhin V displaystyle V nbsp iz soboyu i raziv Tobto V i displaystyle V i nbsp mozhna rozumiti yak mnozhinu vsih ryadkiv sho mozhut buti predstavleni yak konkatenaciya i ryadkiv z V displaystyle V nbsp Viznachennyam zirki Klini na V displaystyle V nbsp ye V i N V i l V 1 V 2 V 3 displaystyle V bigcup i in mathbb N V i left lambda right cup V 1 cup V 2 cup V 3 cup ldots nbsp Tobto ce nabir vsih mozhlivih ryadkiv skinchennoyi dovzhini utvorenih z simvoliv z V displaystyle V nbsp V deyakih doslidzhennyah formalnih mov vikoristovuyetsya riznovid operaciyi Klini zvanij plyus Klini Plyus Klini upuskaye utochniti term V 0 displaystyle V 0 nbsp v poperednomu ob yednanni Inshimi slovami plyus V displaystyle V nbsp ce V i N 0 V i V 1 V 2 V 3 displaystyle V bigcup i in mathbb N setminus 0 V i V 1 cup V 2 cup V 3 cup ldots nbsp Dodatkovo zirka Klini vikoristovuyetsya v teoriyi optimalnosti Prikladi RedaguvatiPriklad zirki Klini zastosovanoyi do mnozhini ryadkiv ab c l ab c abab abc cab cc ababab ababc abcab abcc cabab cabc ccab ccc Priklad zirki Klini zastosovanoyi do mnozhini bukv a b c l a b c aa ab ac ba bb bc ca cb cc Priklad zirki Klini zastosovanoyi do porozhnoyi mnozhini l displaystyle varnothing lambda nbsp Priklad plyusa Klini zastosovanogo do porozhnoyi mnozhini displaystyle varnothing varnothing varnothing varnothing nbsp Zauvazhimo sho dlya kozhnoyi mnozhini L L displaystyle L nbsp dorivnyuye konkatenaciyi L z L displaystyle L nbsp I navpaki L displaystyle L nbsp mozhna zapisati yak l L displaystyle lambda cup L nbsp Operatori L displaystyle L nbsp i L displaystyle L nbsp opisuyut odnu mnozhinu todi i tilki todi yaksho mnozhina L mistit porozhnye slovo Uzagalnennya RedaguvatiRyadki utvoryuyut monoyid z konkatenaciyeyu yak binarnoyu operaciyeyu i nejtralnim elementom l Zirka Klini viznachena dlya bud yakogo monoyida ne tilki ryadkiv Bilsh tochno nehaj M displaystyle M cdot nbsp ce monoyid i S M displaystyle S subseteq M nbsp Todi S displaystyle S nbsp najmenshij monoyid M displaystyle M nbsp sho mistit S displaystyle S nbsp takij sho S displaystyle S nbsp mistit nejtralnij element z M displaystyle M nbsp mnozhinu S displaystyle S nbsp i takij sho yaksho x y S displaystyle x y in S nbsp todi x y S displaystyle x cdot y in S nbsp Div takozh RedaguvatiVisota iteraciyi moviPrimitki Redaguvati Viznachennya na planetmath org Arhiv originalu za 29 travnya 2015 Procitovano 29 travnya 2015 Otrimano z https uk wikipedia org w index php title Zirochka Klini amp oldid 36057447