Слово (формальный язык)

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

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

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

Шаблон:Нет интервики