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

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

1. Если V это набор строк, тогда V^* определяется как наименьший суперсет из V который содержит пустой строкой ε и является закрыто под операция конкатенации строк.
2. Если 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]

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

• Подстановочный знак
• Glob (программирование)

Рекомендации

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

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