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

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

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

[math]\displaystyle{ A^* = \bigcup_{n=0}^{+\infty}A^n. }[/math]

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