Нормальные алгоритмы Маркова . Назначение Объяснение "нормальности" алгоритмов Маркова. Состав системы команд.

Нормальные алгоритмы являются вербальными, то есть предназначенными для применения к словам в различных алфавитах.
Определение всякого нормального алгорифма состоит из двух частей: определения алфавита алгорифма (к словам из символов которого алгорифм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной. Простыми формулами подстановки называются слова вида, где и — два произвольных слова в алфавите алгорифма (называемые, соответственно, левой и правой частями формулы подстановки) . Аналогично, заключительными формулами подстановки называются слова вида, где и — два произвольных слова в алфавите алгорифма. При этом предполагается, что вспомогательные буквы и не принадлежат алфавиту алгорифма (в противном случае на исполняемую ими роль разделителя левой и правой частей следует избрать другие две буквы).