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