Участник: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.