Определение нормального алгоритма Маркова и порядок его работы.

Определение. Нормальный алгоритм Марковазадается алфавитом A в котором он работает и списком подстановок. Список подстановок это функциональная схема алгоритма. Так же как МТ каждый НАМ предназначен для решения задач определенной массовой проблемы.

Порядок работы.

Порядок работы НАМ N над словом (там знак , не могу исправить) состоит из выполнения одним за другим однотипных шагов. На шаге i=0 зарождается исходное слово на последующих шагах функциональная схема алгоритма применяется к и перерабатывает его в

|

Таким образом в процессе работы алгоритма получается последовательность слов:

Процесс работы НАМ заканчивается после выполнения шага K=0, 1, 2,... На слове , если на шаге k осуществимо действие заключительной перестановки или на шаге k+1 список подстановок не может переработать слово