Нормальный алгоритм Маркова

Понятие "нормальный алгоритм" ввел в 1947 г. советский ученый А.А. Марков в качестве одного из уточнений представления об алгоритме. Он положил, что нормальный алгоритм, являясь алгоритмом в некотором алфавите V_T, порождает в нем некоторый детерминированный процесс переработки только одного слова Р_о и только в одном алфавите. Словами Р_i в алгоритме Маркова могут быть арифметические, алгебраические или логические выражения.

Нормальный алгоритм Маркова есть указание использовать упорядоченный список правил подстановки: α_i⇒b_i, где a_i и b_i — некоторые слова в алфавите V_T.

Множество правил и порядок их использования позволяют выполнять преобразования исходного слова Р_о в заключительное слово Q, т.е. Р_о→P₁→P₂→…→P_i→...→Q.

Для организации последовательного и упорядоченного просмотра правил последние должны быть индексированы i∈{1, 2, 3,...}.

Если слово Р_i есть цепочка вида (g₁a_ig₂) в алфавите V_т, где g₁ и g₂ – слова в этом же алфавите и среди множества правил первым в упорядоченном списке есть правило a_i⇒b_i, то нужно выполнить подстановку (g₁a_ig₂)⇒(g₁b_i g₂).

Суть упорядоченного использования правил состоит в том, что каждое переработанное слово вновь поступает в «начало» алгоритма и вновь проверяется на подстановку правил в соответствии с протоколом.

Среди множества правил выделяют заключительное α_i→•b_i, результатом подстановки которого формируется слово Q и дается указание об окончании работы алгоритма.

Процесс может оборваться на некотором слове Р_i, для которого нет соответствующего правила. Тогда это слово направляется в «тупик».

Для того чтобы построить модель алгоритма, необходимо выделить упорядоченную последовательность левых частей правил подстановки, так называемых распознавателей вхождения слов α_i в слово P_i, и множество соответствующих операторов подстановки слова b_i в слово P_i+1.

На схеме алгоритма эти блоки обозначены так: • распознаватели вхождения - PB_i; • операторы подстановки – ОП_i:

Распознаватели вхождения соединяются последовательно в соответствии с заданной последовательностью правил. Второй выход распознавателя вхождения при обнаружении α_i в слове Р_i передает информацию о слове P_i=g₁a_ig₂ в ОП_i, где выполняется соответствующая замена слова α_iна слово b_i, т.е. g₁a_ig₂⇒g₁b_ig₂=P_i+1.

Оператор подстановки направляет слово P_i+1 в «начало» алгоритма, если применена простая подстановка, и в «конец» алгоритма, если применена заключительная подстановка.

Пример. Преобразовать цифры десятичного числа в унарный код.

Если Р_о=#X₁Х₂Х₃...#, где X₁,Х₂,Х₃,… - цифры, то Q=#|^x1#|^x2#|^x3#..., где |^xi – означает x_i «палочек» унарного кода. Алфавит V_T для преобразования цифры в код содержит символы V_т ={X, #, |, (}. Ниже приведена схема этого алгоритма: