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

Алфавитом будем называть любое непустое множество. Его элементы называются буква­ми, а любые последовательности букв - словами в данном алфа­вите. Для удобства рассуждений допускаются пустые слова (они не имеют в своем составе ни одной буквы). Пустое слово (пустой символ) обозначается как . Если А и В — два алфавита, причем А В, то алфа­вит В называется расширением алфавита А.

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

Марковской подстановкой называется опера­ция над словами, задаваемая с помощью упорядоченной пары слов (Р, Q), состоящая в следующем:

1) В заданном слове R находят первое вхождение слова Р (если таковое имеется);

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

Пример. Примеры марковских подстановок рассмотрены в таблице, в каждой строке которой сначала дается преобразуемое слово, затем применяемая к нему марковская подстановка и, на­конец, получающееся в результате слово:

Преобразуемое слово	Марковская подстановка	Результат
138 578 926	(8 578 9, 00)	130 026
тарарам	(ара, )	трам
шрам	(ра, ар)	шарм
функция	( , )	функция
логика	(ика, )	лог
книга	( )	книга
поляна	(пор, т)	[неприменима]

Для обозначения марковской подстановки (Р, Q) использует­ся запись . Она называется формулой подстановки (Р, Q). Подстановки вида будем называть заключительны­ми. Для обозначения таких подстановок будем использовать запись , называя ее формулой заключительной подстановки. Слово Р называется левой частью, a Q -правой частью в формуле подстановки.

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

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

Нормальным алгоритмом Маркова в алфави­те А называется следующее правило построения последователь­ности Vi слов в алфавите А, исходя из данного слова V в этом алфавите. В качестве начального слова V₀ последовательности бе­рется слово V. Пусть для некоторого слово Vi построено и процесс построения рассматриваемой последовательности еще не завершился. Если при этом в схеме нормального алгоритма нет формул, левые части которых входили бы в V_i то V_i+1 полагают равным V_i, и процесс построения последовательности считается завершившимся. Если же в схеме имеются формулы с левыми ча­стями, входящими в V_i, то в качестве V_i+l берется результат мар­ковской подстановки правой части первой из таких формул вме­сто первого вхождения ее левой части в слово V_i. Процесс построения последовательности считается завершившимся, если на данном шаге была применена формула заключительной подстанов­ки, и продолжающимся- в противном случае. Если процесс построения упомянутой последовательности обрывается, то говорят, что рассматриваемый нормальный алгоритм применим к слову V. Пос­ледний член W последовательности называется результатом при­менения нормального алгоритма к слову V. Говорят, что нормальный алгоритм перерабатывает V в W.

Последовательность V_i, будем записывать следующим образом: .

Если алгоритм Маркова задан в некотором расширении алфавита А, то он называется - нормальный алгоритм над алфавитом А.

Рассмотрим примеры нормальных алгоритмов.

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

Рассмотрим последовательность слов: aabab → abab. Всякое слово V в алфавите А, содержащее хотя бы одно вхождение буквы а, он перерабатывает в слово, получа­ющееся из V вычеркиванием в нем самого левого (первого) вхожде­ния буквы а. Пустое слово он перерабатывает в пустое. Алгоритм не применим к таким словам, которые содержат только букву b.

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

Рассмотрим последовательность слов: bab → abab → aabab → aacab. Первая подстановка применима всегда, т. к. пустой символ мы можем приписать слева от любого слова.

Пример. Пусть A = {a₀, a₁ ..., a_n} — алфавит. Рассмотрим схему:

Она определяет нормальный алгоритм, перерабатывающий вся­кое слово (в алфавите А) в пустое слово: .

Как и машины Тьюринга, нормальные алгоритмы не про­изводят вычислений, а производят преобра­зования слов, заменяя в них одни буквы другими по предписан­ным им правилам, результаты применения которых можно интерпрети­ровать как вычисления.

Пример. В алфавите А = {1} схема определяет нор­мальный алгоритм, который к каждому слову в алфавите А = {1}, вида: , 1, 11, 111, 1111, 11111 и т. д., приписывает слева 1. Следовательно, алгоритм реализует (вычис­ляет) функцию .

Пример. Пусть A = {a, b, с, d} — алфавит. Рассмотрим схему:

Данная схема удаляет из слова все вхождения символа c, после чего заменяется bb на ddd, затем алгоритм остановится: сbaсbb → babb → baddd.

Задание