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

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

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

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

Например:

a = алгоритм - слово в алфавите А;

b = 1010100 - слово в алфавите В;

g = DD+0 - слово в алфавите С.

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

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

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

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

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

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

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

, где - слова в алфавите А.

Например: в слове 1012011201 два вхождения слова 12, три вхождения слова 01, одиннадцать вхождений пустого слова L - перед первой, после последней букв и между всеми буквами.

Слово a называется началом слова b, если ; концом слова b, если .

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

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

Дата добавления: 2014-01-07