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

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

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

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

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

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

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

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

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

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

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

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

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