Лекция: Пример (с49).

Нормальные алгоритмы и их применение к словам.

Упорядоченный конечный список формул подстановок (с50)

в алфавите А называется схемой нормального алгоритма в А. (Запись точки в скобках означает, что она может стоять в этом месте, а может отсутствовать.) Данная схема определяет (детерминирует) алгоритм преобразования слов, называемый нормальным алгоритмом Маркова.

Нормальным алгоритмом (Маркова) в алфавите А называется следующее правило построения последовательности Vi слов в алфавите А, исходя из данного слова V в этом алфавите. В качестве начального слова V0 последовательности берется слово V. Пусть для некоторого i >= 0 слово Vi построено и процесс построения рассматриваемой последовательности еще не завершился.

При этом, если в схеме нормального алгоритма нет формул, левые части которых входили бы в Vi, то Vi+1 полагают равным Vi, и процесс построения последовательности считается завершившимся, если же в схеме имеются формулы с левыми частями, входящими в Vi, то в качестве Vi+1, берется результат марковской подстановки правой части первой из таких формул вместо первого вхождения ее левой части в слово Vi. Процесс построения последовательности считается завершившимся, если на данном шаге была применена формула заключительной подстановки, и продолжающимся — в противном случае.

Если процесс построения упомянутой последовательности обрывается, то говорят, что рассматриваемый нормальный алгоритм применим к слову V. Последний элемент W последовательности называется результатом применения нормального алгоритма к слову V. Говорят, что нормальный алгоритм перерабатывает V B W.

Последовательность Vi, будем записывать следующим образом:

V0 => V1 => V2 =>… => Vm-1 => Vm,

где V0 = V и Vm = W.