Формализация нормального алгорифма Маркова

Запишем один из способов формальной записи связного алгоритма для нормального алгорифма Маркова (одного из стандартных способов формального определения понятия "алгоритм").

Абстрактная вычислительная машина, реализующая нормального алгорифма Маркова, представляет собой несколько элементов:

строка символов конечного алфавита;

конечная упорядоченная последовательность правил подстановки.

Взаимодействие между строкой и последовательностью правил подстановки обусловлено:

текущей рабочей формулой подстановки;

наличие или отсутствие в строке искомого слова, указываемого в левой части рабочей формулы подстановки.

Результатом взаимодействия в случае наличия искомого слова в строке становится:

замена крайнего левого найденного в строке слова на слово, содержащееся в правой части рабочей формулы;

остановка исполнения в случае терминальной метки на рабочей формуле;

установление первой формулы последовательности в качестве рабочей формулы.

Результатом взаимодействия в случае отсутствия слова в строке становится:

установление следующей за текущей по порядку формулы последовательности в качестве рабочей формулы, если следующая существует;

остановка работы, если следующей по порядку формулы нет.

Продумать режим работы с необходимостью изменения количества объектов (в строке). Возможная реализация - бесконечный ресурсный буфер объектов.

Формализация нормального алгорифма Маркова

Report Page