Слово (математика)

У этого термина существуют и другие значения, см. Слово (значения).

Слово в дискретной математике — это любой конечный упорядоченный набор (кортеж) символов из данного алфавита. Число символов в слове $\alpha$ называют его длиной и обозначают $|\alpha|$. Существует единственное слово длины 0, называемое пустым словом. Оно не содержит ни одного символа и обозначается буквой $e$, $\varepsilon$ или $\Lambda$.

Множество всех слов длины $n$ в алфавите $A$ обозначают через $A^n$ (см. также Декартово произведение множеств). Множество всех слов в алфавите $A$ (произвольной длины) обозначают через $A^*$. Из определения следует, что

$A^* = \bigcup_{n=0}^{+\infty}A^n$

На словах в данном алфавите $A$ определена операция конкатенации (склеивания слов). Множество всех слов в алфавите $A$ с операцией конкатенации образует моноид. Множество всех непустых слов в алфавите $A$ с операцией конкатенации образует полугруппу.