'''Алфавит''' {{---}} конечное непустое множество символов. Условимся обозначать алфавит символом <tex>\Sigma</tex>.
}}
Наиболее часто используются следующие алфавиты:
# <tex>\Sigma=\{0, 1\}</tex> {{---}} бинарный или двоичный алфавит.
'''Длина цепочки''' {{---}} число символов в цепочке. Длину некоторой цепочки <tex>w</tex> обычно обозначают <tex>|w|</tex>.
}}
Если <tex>\Sigma</tex> {{---}} некоторый алфавит, то можно выразить множество всех цепочек определенной длины, состоящих из символов данного алфавита, используя знак степени. Определим <tex>\Sigma^k</tex> как множество всех цепочек длины <tex>k</tex>, состоящих из символов алфавита <tex>\Sigma</tex>. Множество всех цепочек над алфавитом <tex>\Sigma</tex> принято обозначать <tex>\Sigma^*</tex>, то есть <tex>\Sigma^*=\{\Sigma^0, \Sigma^1, \Sigma^2, ...\}</tex>.
{{Определение
|definition =
Пусть <tex>x\Sigma^k</tex> {{---}} множество цепочек длины <tex>k</tex> и над алфавитом <tex>y\Sigma</tex> .}} {{Определение|definition =<tex>\Sigma^* = \bigcup \limits _{---k=0}^\infty \Sigma^k</tex> — множество всех цепочек над алфавитом <tex>\Sigma</tex>.}} цепочки {{Определение|definition =Пусть <tex>x, y \in \Sigma^*</tex>. Тогда <tex>xy</tex> обозначает их '''конкатенацию''', т.е. цепочку, в которой последовательно записаны цепочки x и y.
}}
