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

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

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

$A^{\ast <!--\; \ast \; -->}=\underset{n=0}{\overset{+\mathrm{\infty <!--\; \infty \; -->}}{\bigcup <!--\; \bigcup \; -->}}{A}^n.$$A^{*}=\bigcup _{n=0}^{+\infty }A^{n}.$

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