Нормальные алгоритмы Маркова

Теория нормальных алгоритмов была разработана советским математиком А.А. Марковым[3] в конце 1940-х – начале 1950-х гг. Эти алгоритмы представляют собой некоторые правила по переработке слов в произвольном алфавите так, что исходные данные и искомые результаты для алгоритмов являются словами в некотором алфавите. Нормальные алгоритмы Маркова являются строгим определением алгоритма, уточняющим интуитивное представление на основе алфавитно-словарного подхода.

 

Марковские подстановки

Алфавитом будем называть любое непустое подмножество, его элементы называются буквами, любые последовательности букв – словами в данном алфавите. Слова, не содержащие букв, будем называть пустыми и обозначать . Если A и B – два алфавита, где , то алфавит B называется расширением алфавита А.

Для обозначения слов будем использовать заглавные буквы латинского алфавита P, Q, R, или эти же буквы с индексами. Одно слово может быть составной частью другого слова. Тогда первое называется подсловом второго или вхождением во второе.

Пример 7.9. Пусть А – алфавит русских букв. Можем рассмотреть слова: P ₁=ПОБЕДА, Р ₂=БЕДА, Р ₃=ДА. Слово Р ₂ является подсловом Р ₁, а Р ₃ – подсловом Р ₁ и Р ₂.

Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов (P, Q), состоящая в следующем. В заданном слове R находят первое вхождение слова P (если такое имеется) и, не изменяя остальных частей слова R, заменяют в нем это вхождение словом Q. Полученное слово называют результатом применения марковской подстановки (P, Q) к слову R. Если же первого вхождения Р в слово R нет (вообще нет ни одного вхождения), то считается, что марковская подстановка (P, Q) не применима к слову R.

Для обозначения марковской подстановки (P, Q) используется запись P Q, которая называется формулой подстановки. Некоторые подстановки P Q называются заключительными и обозначаются P ž Q, и называются формулы заключительной подстановки. При этом символы «»,«ž» не являются символами алфавита А. Слово Р называется левой частью подстановки, Q – правой частью.

 

Пример 7.10.

	Преобразуемое слово	Подстановка	Результат
		3456 00
	тарарам	ара	трам
	шрам	ра ар	шарм
	функция		функция
	сумма		сумма
	клубника	пор т	не применима

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

(7.7)

в алфавите А называется схемой нормального алгоритма в алфавите А.

Запись точки в скобках обозначает, что она может стоять в этом месте, а может и отсутствовать. Схема (7.7) определяет алгоритм преобразования слов, называемый нормальным алгоритмом Маркова.

Нормальным алгоритмом Маркова в алфавите А называется следующее правило построения последовательности R_i слов в алфавите А, исходя из данного слова R в этом алфавите. В качестве начального слова R ₀ последовательности берется слово R. Пусть для любого слово R_i построено и процесс построения рассматриваемой последовательности не завершился. Если при этом в схеме нормальных алгоритмов нет формул, левые части которых входили бы в R_i, то R_{i +1} полагают равным R_i и процесс построения последовательности считается завершившимся. Если же в схеме имеются формулы с левыми частями, входящими в R_i, то в качестве R_{i +1} берется результат марковской подстановки правой части первой из таких формул вместо первого вхождения её левой части в слово R_i.

Процесс построения последовательности считается завершившимся, если на данном шаге была применена формула заключительной подстановки и продолжающимся – в противном случае. Если процесс построения последовательности обрывается, говорят, что рассматриваемый нормальный алгоритм применим к слову R. Последний член последовательности называется результатом применения нормального алгоритма к слову R.

Таким образом, определили понятие нормального алгоритма в алфавите А. Если же алгоритм задан в некотором расширении алфавита А, то говорят, что он есть нормальный алгоритм над алфавитом А.

 

Пример 7.11. Пусть А ={ a, b } – алфавит. Рассмотрим следующую схему нормального алгоритма в А

Видно, что всякое слово R в алфавите А, содержащее хотя бы одно вхождение буквы а, нормальный алгоритм перерабатывает в слово, получающееся из R вычеркиванием самого левого (первого) вхождения буквы а. Алгоритм не применим к таким словам, которые содержат только букву b (никогда не останавливается). Пример работы нормального алгоритма Маркова: ; ; .

 

Пример 7.12. Пусть А ={1,+} – алфавит. Рассмотрим следующую схему нормального алгоритма в А:

Рассмотрим применение нормального алгоритма к слову Р = 11+111:

первая подстановка,

первая подстановка,

вторая подстановка,

.

Получим слово . Данный нормальный алгоритм выполняет сложение двух натуральных чисел в унарной системе счисления.

Для того чтобы складывать несколько чисел, записанных через знак «+» в исходном слове, нормальный алгоритм должен иметь вид:

Рассмотрим применение этой схемы к слову Р = 1+11+1:

первая подстановка,

первая подстановка,

первая подстановка,

первая подстановка,

вторая подстановка,

третья подстановка,

1111.