Алгебра Клини

Перейти к навигацииПерейти к поиску

Алгебра Клини  — специальная алгебраическая структура, введённая Стивеном Клини как обобщение алгебры регулярных выражений; широко используется в теоретической информатике.

Определяется как алгебра сигнатуры , являющаяся (некоммутативным) идемпотентным полукольцом (с единицей), то есть, удовлетворяющая аксиомам:

для которой справедливы также четыре новых аксиомы:

  • ,
  • ,
  • ,
  • ,

где частичный порядок задан эквивалентностью . Операция «*» называется итерацией или звездой Клини (англ. Kleene star).

Алгебра регулярных выражений — стандартный пример алгебры Клини: со множествами строк (над некоторым фиксированным алфавитом) в качестве элементов, 0 — пустое множество, 1 — множество, состоящее из одного пустого символа, сложение интерпретируется как теоретико-множественное объединение, умножение задаётся формулой , где  — операция конкатенации строк. Итерация задаётся как объединение всех множеств .

Литература