Клини звезда - Kleene star

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

Если V это набор строк, тогда V^* определяется как наименьший суперсет из V который содержит пустой строкой ε и является закрыто под операция конкатенации строк.
Если V представляет собой набор символов или знаков, тогда V^* это набор всех строк над символами в V, включая пустую строку ε.

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

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

Определение и обозначения

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

V⁰ = {ε} (язык, состоящий только из пустой строки),

V¹ = V

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

V^я+1 = { wv : ш ∈ V^я и v ∈ V } для каждогоя > 0.

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

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

{displaystyle V ^ {*} = igcup _ {igeq 0} V ^ {i} = V ^ {0} чашка V ^ {1} чашка V ^ {2} чашка V ^ {3} чашка V ^ {4} чашка cdots.}

Это означает, что звездный оператор Клини является идемпотент унарный оператор: (V^*)^* = V^* для любого набора V строк или символов, как (V^*)^я = V^* для каждого я≥1.

Клини плюс

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

{displaystyle V ^ {+} = igcup _ {igeq 1} V ^ {i} = V ^ {1} чашка V ^ {2} чашка V ^ {3} чашки cdots.}

или же

{displaystyle V ^ {*} setminus V ^ {0} = V ^ {+} = V ^ {*} V}

^[3]

Примеры

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

{"ab", "c"}^* = {ε, «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» "," ааа "," ааб ", ...}.

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

∅^* = {ε}.

Пример применения Kleene plus к пустому набору:

∅⁺ = ∅ ∅^* = { } = ∅,

где конкатенация - это ассоциативный и некоммутативный продукт, разделяя эти свойства с Декартово произведение наборов.

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

Если V = {ε}, то также V^я = {ε} для каждого я, следовательно, V^* = V⁺ = {ε}.

Обобщение

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

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

Смотрите также

дальнейшее чтение

Хопкрофт, Джон Э.; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Эддисон-Уэсли.

[1] Наюки Минасе (10 мая 2011 г.). «Счетные множества и звезда Клини». Проект Наюки. Получено 11 января 2012.

[2] Эббингаус, Хайнц-Дитер; Флум, Йорг; Томас, Вольфганг (1994). Математическая логика (2-е изд.). Нью-Йорк: Springer. п. 656. ISBN 0-387-94258-0. В Клини закрытие L^* из L определяется как ${displaystyle sideset {} {_ {i = 0} ^ {infty}} igcup L ^ {i}}$ .

[3] Правильное уравнение выполняется, потому что каждый элемент V⁺ должен состоять из одного элемента V и конечное число непустых членов в V или это просто элемент V (куда V сам извлекается, принимая V соединенный с ε).

[droste-4] Droste, M .; Куич, В. (2009). «Глава 1: Полукольца и формальные степенные ряды». Справочник по взвешенным автоматам. Монографии по теоретической информатике. Springer. п.9. Дои:10.1007/978-3-642-01492-5_1. ISBN 978-3-642-01491-8.

[1]

[2]

[3]

[4]