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

Шаблон:Другие значения Сло́во формального языка (также — цепочка, строка) — произвольная последовательность символов из данного алфавита. Число символов в слове $\alpha$ называют его длиной и обозначают $|\alpha |$. Может допускаться существование единственного слова длины 0, (пустое слово), не содержащее ни одного символа (обозначается $e$, $\epsilon$ или $\mathrm{\Lambda }$).

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

$A^{*}=\bigcup _{n=0}^{+\mathrm{\infty }}{A}^n.$

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