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

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

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

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

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