Структуры данных и модели вычислений



         

Алгорифмы Маркова


Термин "алгорифм" является устаревшим вариантом современного термина "алгоритм", однако по отношению к алгоритмам Маркова принято использовать авторский вариант.

Информация, обрабатываемая алгорифмом Маркова, представляется словом в некотором фиксированном алфавите .

Алгорифм (программа) представляется последовательностью пар слов в алфавите . Пары, составляющие алгорифм, называются также подстановками и записываются в виде

где , — слова в алфавите , причем может быть пустым (обозначаем ). Программа имеет вид

Некоторые подстановки помечаются восклицательным знаком и называются заключительными.

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

Замечание.

Алгорифмы Маркова составляют теоретическую основу системы программирования, использующую язык РЕФАЛ.

Пример.

Алфавит . Здесь запятая не является символом алфавита.

Рассмотрим программу

Убедитесь в том, что она входное слово вида переработает в слово , в котором число символов "1" — такое же, как во входном слове. Можно считать, что программа выполняет сложение натуральных чисел, представленных в унарной системе счисления.

Пример.

Алфавит .

Программа

Рассмотрим протокол вычислений на входном слове . Справа указаны применяемые подстановки.

Если считать, что во входном слове закодирована задача умножения в унарной системе счисления, то в выходном слове получен ответ 6.

Докажите, что программа дает верный ответ при любом корректном входном слове.




Содержание  Назад  Вперед