Теория алгоритмов, формальных языков, грамматик и автоматов. Бильгаева Н.Ц. - 5 стр.

Поэтому алгоритмами в современной математике принято называть конструктивно
задаваемые соответствия между изображениями объектов в абстрактных алфавитах.
    Абстрактным алфавитом называется любая конечная совокупность объектов,
называемых буквами или символами данного алфавита. При этом природа этих объектов нас
совершенно не интересует. Символом абстрактных алфавитов можно считать буквы
алфавита какого-либо языка, цифры, любые значки и даже слова некоторого конкретного
языка. Основным требованием к алфавиту является его конечность. Таким образом, можно
утверждать, что алфавит - это конечное множество различных символов. Алфавит, как
любое множество, задается перечислением его элементов.
    Итак, объекты реального мира можно изображать словами в различных алфавитах. Это
позволяет считать, что объектами работы алгоритмов могут быть только слова. Тогда можно
сформулировать следующее определение.
    Алгоритм есть четкая конечная система правил для преобразования слов из некоторого
алфавита в слова из этого же алфавита.
    Слово, к которому применяется алгоритм, называется входным. Слово, вырабатываемое
в результате применения алгоритма, называется выходным.
    Совокупность слов, к которым применим данный алгоритм, называется областью
применимости этого алгоритма.
    Формальные определения алгоритма появились в 30-х - 40-х годах XX века. Можно
выделить три основных типа универсальных алгоритмических моделей, различающихся
исходными эвристическими соображениями относительно того, что такое алгоритм. Первый
тип связывает понятие алгоритма с наиболее традиционными понятиями математики -
вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого типа -
рекурсивные функции - является исторически первой формализацией понятия алгоритма.
Эта модель основана на функциональном подходе и рассматривает понятие алгоритма с
точки зрения того, что можно вычислить с его помощью.
    Второй тип основан на представлении алгоритма как некоторого детерминированного
устройства, способного выполнять в каждый отдельный момент некоторые примитивные
операции, или инструкции. Такое представление не оставляет сомнений в однозначности
алгоритма и элементарности его шагов. Основной теоретической моделью этого типа,
созданной в 30-х годах, является машина Тьюринга, которая представляет собой
автоматную модель, в основе которой лежит анализ процесса выполнения алгоритма как
совокупности набора инструкций.
    Третий тип алгоритмических моделей - это преобразования слов в произвольных
алфавитах, в которых элементарными операциями являются подстановки, т.е. замены части
слова (подслова) другим словом. Преимущество этого типа состоит в его максимальной
абстрактности и возможности применить понятие алгоритма к объектам произвольной
природы. Модели второго и третьего типа довольно близки и отличаются в основном
эвристическими подходами. Примерами моделей этого типа являются              нормальные
алгоритмы Маркова и канонические системы Поста.

      1.4. Понятие алфавитного оператора
    Понятие алфавитного оператора является наиболее общим. К нему фактически сводятся
любые процессы преобразования информации. К изучению алфавитных операторов
фактически сводится теория любых преобразователей информации. Основой теории
алфавитных операторов являются способы их задания. Если область определения
алфавитного оператора конечна, то оператор может быть задан простой таблицей
соответствия. В случае бесконечной области определения алфавитного оператора он задается
системой правил, позволяющей за конечное число шагов найти выходное слово,
соответствующее заданному входному слову. Алфавитные операторы, задаваемые с
помощью конечной системы правил, называются алгоритмами.