Символьные конструкции

Алфавитомбудем называть любое конечное множество попарно различных знаков, называемых буквами (символами) этого алфавита. Алфавит будем обозначать заглавными буквами, например:

Символом l будем обозначать пустой символ.

Словомв данном алфавите называется любая конечная (в том числе и пустая) последовательность букв этого алфавита. Слова будем обозначать малыми греческими буквами.

Например: a = алгоритм – слово в алфавите А; b = 1010100 – слово в алфавите В; – слово в алфавите С.

Пустое слово будем обозначать L.

Длинаслова a (обозначается ) – это количество букв в слове.

Определим некоторые отношения и операции над словами.

Равенство словв алфавите А определяется индуктивно:

а) пустые слова равны

б) если слово a равно слову b, то a b =bb , где b –буква в алфавите А.

Если слово a является частью слова b, то говорят, что имеет место вхождениеслова a в слово b (слово a называется подсловом слова b). Это можно записать следующим образом: , где – слова в алфавите А.

Слово a называется началом слова b, если ; концомслова b, если . Слово длины n, составленное из буквы а, повторенной n раз, будем обозначать , например xyxxxyyyy = .

Операция (и результат) приписывания слов a и b друг к другу называется конкатенацией(обозначается a||b). Например, если .