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

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

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

Нормальные алгоритмы и их применение к словам.Упорядо­ченный конечный список формул подстановок

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

Определение 2. Нормальным алгоритмом (Маркова) в алфавите А называется следующее правило построения последовательности V_i слов в алфавите А, исходя из данного слова V в этом алфавите. В качестве начального слова V₀ последовательности бе­рется слово V. Пусть для некоторого i >= 0 слово V_i построено и процесс построения рассматриваемой последовательности еще не завершился. Если при этом в схеме нормального алгоритма нет формул, левые части которых входили бы в V_i , то V_i+1 полагают равным V_i и процесс построения последовательности считается завершившимся. Если же в схеме имеются формулы с левыми ча­стями, входящими в V_i, то в качестве V_i+1, берется результат мар­ковской подстановки правой части первой из таких формул вме­сто первого вхождения ее левой части в слово V_i; процесс постро­ения последовательности считается завершившимся, если на дан­ном шаге была применена формула заключительной подстанов­ки, и продолжающимся — в противном случае. Если процесс построения упомянутой последовательности обрывается, то говорят, что рассматриваемый нормальный алгоритм применим к слову V. Пос­ледний член W последовательности называется результатом при­менения нормального алгоритма к слову V. Говорят, что нормальный алгоритм перерабатывает V b W.

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

V₀ => V₀ => V₂ => ... => V_m-1 => V_m,

где V₀ = V и V_m = W.

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