Фиксируем некоторый алфавит 
. Пусть символы «стрелка» и «точка» не принадлежат алфавиту : 
, 
. 
– некоторые, возможно пустые, слова в алфавите .
Марковская подстановка (МП) – это операция над словами 
, заключающаяся в следующем:
1) в исходном слове 
ищется самое левое вхождение слова 
, если оно существует, заменяем на 
в слове ;
2) полученное слово 
является результатом применения марковской подстановки к слову 
;
3) если слово не входит в слово , то говорят, что данная Марковская подстановка неприменима к слову .
Обычно МП записывается как 
.
в общем случае длины слов 
могут не совпадать.
длины слов 
в общем случае также могут не совпадать.
Если 
или 
, то соответствующее слово является пустым. В МП пустое слово никак не обозначается и не занимает никакого места.
В любом слове имеется несколько вхождений пустого слова: перед первой буквой; после последней буквы; между любой парой букв внутри слова.
Частные случаи МП:
1. 
, – пусто: слово приписывается перед 
.
2. 
, – пусто: слово исключается из .
Нормальным алгоритмом Маркова (НАМ) в алфавите называется упорядоченная конечная последовательность (столбец) Марковских подстановок типа: или (и) 
, где – слова в алфавите , а символы 
и 
.
– заключительная подстановка.
Запись НАМ – столбец подстановок вида 
.
