В современной математике алгоритмами принято называть конструктивно задаваемые соответствия между словами в абстрактных алфавитах. Это определение, в свою очередь, использует два понятия – понятие абстрактного алфавита и слов в таком алфавите.
Абстрактным алфавитом называется любая конечная совокупность объектов, называемых буквами или символами данного алфавита. Иными словами алфавит - это конечное множество различимых символов (слово "абстрактный" для краткости здесь и далее опускается). Алфавит, как и любое другое множество, может быть задан перечислением его элементов. Например, алфавит A есть A={a, b, c}, алфавит B есть B={x, y}.
Под словом или строкой в алфавите понимают любую конечную последовательность символов. В последовательности (цепочке) между символами стоит операция сцепки или конкатенации, т.е. менять местами символы в последовательности нельзя. Например, в алфавите А словами являются любые последовательности: a, ac, cb, acb, bb, а в алфавите B: x, y, yx, xx и т. п.
Число символов в слове называется длиной этого слова. Так слова в алфавите А, приведенные в примере, имеют длину соответственно 1, 2, 2, 3, 2. Различают также пустые слова, не содержащие ни одного символа. Слово р называется подсловом слова q, если слово q можно представить в виде q=pr, где r - любое слово, в том числе и пустое. Очевидно, что такое понятие слова будет отличаться от аналогичного в разговорных языках. Здесь под словом можно понимать любую последовательность символов, даже бессмысленную.
При расширении алфавита понятие слова может существенно меняться. Так, например, в алфавите A={0,1,2,3,4,5,6,7,8,9} цепочка символов 69+73 представляет собой два слова, соединенные знаком суммы, а в алфавите В={+,0,1,2,3,4,5,6,7,8,9} это будет одно слово.
Алфавитным оператором или алфавитным отображением называется всякое соответствие между словами некоторого алфавита и словами в том же самом или в каком-либо другом фиксированном алфавите. Первый называется входным, а второй – выходным алфавитом данного оператора. В случае совпадения входного и выходного алфавитов говорят, что алфавитный оператор задан в соответствующем алфавите.
Пусть заданы слова в алфавитах X и Y и заданы соответствия между этими словами. Если xi – слово в алфавите X, а yj – слово в алфавите Y, то алфавитный оператор Гxi=yj преобразует входное слово xi в выходное слово yj. Символ Г в алфавитном операторе означает отображение.
Различают однозначные и многозначные алфавитные операторы. Под однозначным алфавитным оператором понимается такой алфавитный оператор, который каждому входному слову ставит в соответствие не более одного выходного слова.
Совокупность всех слов, на которых алфавитный оператор определен, называется областью его определения. Алфавитный оператор, не сопоставляющий данному входному слову ai никакого выходного слова bj (в том числе и пустого), на этом слове не определен.
|
