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

Упорядоченный конечный список формул подстановок в алфавите А называется схемой нормального алгоритма в А

Для задания нормального алгоритма необходимо определить:
- алфавит (к словам в котором алгоритм будет применяться)
- схему алгоритма

Процесс применения нормального алгоритма к произвольному слову представляет собой дискретную последовательность элементарных шагов (тактов)

Пусть R - слово, полученное на предыдущем шаге работы алгоритма (или исходное слово, если текущий шаг является первым).
Шаг работы нормального алгоритма
1) Если в схеме алгоритма среди формул подстановки нет такой, левая часть которой входила бы в R, то работа алгоритма считается завершённой, и результатом этой работы считается слово R
2) Если в схеме алгоритма имеются формулы подстановки, левые части которых входят в R, то к слову R применяется марковская подстановка, соответствующая первой такой формуле в схеме