Jump to content

Клини звезда

(Перенаправлено с «Клин плюс »)

В математической логике и информатике звезда Клини (или оператор Клини , или замыкание Клини — это унарная операция , выполняемая либо над наборами строк ) , либо над наборами символов или символов. В математике,она более известна как конструкция свободного моноида . Применение звезды Клини к набору написано как . Он широко используется для регулярных выражений , в контексте которого он был введен Стивеном Клини для характеристики определенных автоматов , где он означает «ноль или более повторений».

  1. Если представляет собой набор строк, то определяется как надмножество наименьшее который содержит пустую строку и закрывается при операции конкатенации строк .
  2. Если представляет собой набор символов или знаков, то — это набор всех строк над символами в , включая пустую строку .

Набор также может быть описан как набор, содержащий пустую строку и все строки конечной длины, которые могут быть сгенерированы путем объединения произвольных элементов , что позволяет использовать один и тот же элемент несколько раз. Если является либо пустым множеством ∅, либо одноэлементным множеством , затем ; если любое другое конечное или счетно бесконечное множество , то является счетным бесконечным множеством. [1] Как следствие, каждый формальный язык в конечном или счетно бесконечном алфавите счетно, так как является подмножеством счетно бесконечного множества .

Операторы используются в правилах перезаписи порождающих грамматик .

Определение и обозначения [ править ]

Учитывая набор ,определять

(язык, состоящий только из пустой строки),
,

и рекурсивно определим множество

для каждого .

Если является формальным языком, то , -я степень множества , является сокращением для объединения множества с самим собой раз. То есть, можно понимать как набор всех строк , которые можно представить как конкатенацию струны в .

Определение звезды Клини на является [2]

Это означает, что звездный оператор Клини является идемпотентным унарным оператором : для любого набора строк или символов, например для каждого .

Клини плюс [ править ]

В некоторых формальных языковых исследованиях (например, в теории AFL вариант операции «звезда Клини», называемый плюс Клини ) используется . В Kleene plus отсутствует термин в вышеуказанном союзе. Другими словами, «Клин плюс» является

или

[3]

Примеры [ править ]

Пример звезды Клини, примененной к набору струн:

{"аб","с"} * = { ε, "ab", "c", "abab", "abc", "cab", "cc", "ababab", "ababc", "abcab", "abcc", "cabab", "cabc" ", "ccab", "ccc", ...}.

Пример использования Kleene plus к набору символов:

{"а", "б", "в"} + = { "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc", «ааа», «ааб», ...}.

Звезда Клини применена к тому же набору символов:

{"а", "б", "в"} * = { ε, "a", "b", "c", "aa", "ab", "ac", "ba", "bb", "bc", "ca", "cb", "cc" ", "ааа", "ааб", ...}.

Пример звезды Клини, примененной к пустому множеству:

* = {е}.

Пример применения «Клин плюс» к пустому множеству:

+ = ∅ ∅ * = { } = ∅,

где конкатенация — ассоциативное и некоммутативное произведение.

Пример Клини плюс и Клини звездочка, примененных к одноэлементному набору, содержащему пустую строку:

Если , тогда также для каждого , следовательно .

Обобщение [ править ]

Строки образуют моноид с конкатенацией в качестве бинарной операции и ε в качестве единичного элемента. Звезда Клини определена для любого моноида, а не только для струн.Точнее, пусть ( M — моноид и S M. , ⋅ ) Тогда С * — наименьший субмоноид M , содержащий S ; то есть С * содержит нейтральный элемент M , множество S , и таков, что если x , y S * , то x y S * .

Более того, звезда Клини обобщается путем включения *-операции (и объединения) в саму алгебраическую структуру посредством понятия полного звездного полукольца . [4]

См. также [ править ]

Ссылки [ править ]

  1. ^ Наюки Минасэ (10 мая 2011 г.). «Счетные множества и Клини Стар » Проект Наюки Получено 11 января.
  2. ^ Флетчер, Питер; Хойл, Хьюз; Пэтти, К. Уэйн (1991). Основы дискретной математики . Брукс/Коул. п. 656. ИСБН  0534923739 . Закрытие Клини L * L как определяется .
  3. ^ Это уравнение справедливо, потому что каждый элемент V + должен либо состоять из одного элемента V и конечного числа непустых термов V , либо быть просто элементом V (где V сам извлекается путем объединения V с ε).
  4. ^ Дросте, М.; Куич, В. (2009). «Глава 1: Полукольца и формальный степенной ряд». Справочник по взвешенным автоматам . Монографии по теоретической информатике. Спрингер. п. 9 . дои : 10.1007/978-3-642-01492-5_1 . ISBN  978-3-642-01491-8 .

Дальнейшее чтение [ править ]

Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: a59dee2fd9e0d1405bbd8c27f48c7e4e__1689688320
URL1:https://arc.ask3.ru/arc/aa/a5/4e/a59dee2fd9e0d1405bbd8c27f48c7e4e.html
Заголовок, (Title) документа по адресу, URL1:
Kleene star - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)