Алфавитомбудем называть любое конечное множество попарно различных знаков, называемых буквами (символами) этого алфавита. Алфавит будем обозначать заглавными буквами, например:
Символом l будем обозначать пустой символ.
Словомв данном алфавите называется любая конечная (в том числе и пустая) последовательность букв этого алфавита. Слова будем обозначать малыми греческими буквами.
Например: a = алгоритм – слово в алфавите А; b = 1010100 – слово в алфавите В; 
– слово в алфавите С.
Пустое слово будем обозначать L.
Длинаслова a (обозначается |a|) – это количество букв в слове.
Определим некоторые отношения и операции над словами.
Равенство словв алфавите А определяется индуктивно:
а) пустые слова равны
б) если слово a равно слову b, то a b =bb , где b –буква в алфавите А.
Если слово a является частью слова b, то говорят, что имеет место вхождениеслова a в слово b (слово a называется подсловом слова b). Это можно записать следующим образом: 
, где 
– слова в алфавите А.
Слово a называется началом слова b, если 
; концомслова b, если 
. Слово длины n, составленное из буквы а, повторенной n раз, будем обозначать 
, например xyxxxyyyy = 
.
Операция (и результат) приписывания слов a и b друг к другу называется конкатенацией(обозначается a||b). Например, если 
.
