Теоретическая справка

Фиксируем некоторый алфавит . Пусть символы «стрелка» и «точка» не принадлежат алфавиту : , . – некоторые, возможно пустые, слова в алфавите .

Марковская подстановка (МП) – это операция над словами , заключающаяся в следующем:

1) в исходном слове ищется самое левое вхождение слова , если оно существует, заменяем на в слове ;

2) полученное слово является результатом применения марковской подстановки к слову ;

3) если слово не входит в слово , то говорят, что данная Марковская подстановка неприменима к слову .

Обычно МП записывается как .

в общем случае длины слов могут не совпадать.

длины слов в общем случае также могут не совпадать.

Если или , то соответствующее слово является пустым. В МП пустое слово никак не обозначается и не занимает никакого места.

В любом слове имеется несколько вхождений пустого слова: перед первой буквой; после последней буквы; между любой парой букв внутри слова.

Частные случаи МП:

1. , – пусто: слово приписывается перед .

2. , – пусто: слово исключается из .

Нормальным алгоритмом Маркова (НАМ) в алфавите называется упорядоченная конечная последовательность (столбец) Марковских подстановок типа: или (и) , где – слова в алфавите , а символы и .

– заключительная подстановка.

Запись НАМ – столбец подстановок вида .