Участник:Shersh/temporary

Материал из Викиконспекты
Перейти к: навигация, поиск

Базовые определения[править]

Определение:
Алфавит (англ. alphabet) [math]\Sigma[/math] — .


Примеры:

  • [math]\Sigma = \left\{0, 1\right\} [/math] — бинарный алфавит.


Определение:
Нейтральный элемент — пустая строка [math]\varepsilon : \varepsilon \in \Sigma^{0}[/math].


Определение:
Замыкание Клини (англ. Kleene closure) — унарная операция над множеством строк либо символов. Замыкание Клини множества [math]\Sigma[/math] есть [math]\Sigma^* : \Sigma^* = \bigcup\limits_{n = 0}^\infty \Sigma^n[/math].


Если [math]\Sigma = \left\{0, 1\right\}[/math], то [math]\Sigma^* = \left\{\varepsilon, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, \dots \right\} [/math].


Определение:
Цепочка (англ. chain) — элемент конечной длины из [math]\Sigma^*[/math].


Определение:
Моноид (англ. monoid) — множество, на котором задана бинарная ассоциативная операция, обычно именуемая умножением, и в котором существует нейтральный элемент. [math]\Sigma^*[/math] с операцией конкатенации и нейтральным элементом [math]\varepsilon[/math] образуют моноид



Литература[править]

  • Gusfield, Dan (1999) [1997]. Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. USA: Cambridge University Press. ISBN 0-521-58519-8.