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



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

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



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

 

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

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

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

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

Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов (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) определяет алгоритм преобразования слов, называемый нормальным алгоритмом Маркова.

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

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

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

 

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

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

 

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

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

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

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

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

.

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

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

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

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

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

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

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

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

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

1111.



Последнее изменение этой страницы: 2016-07-14; просмотров: 793; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 34.228.229.51 (0.018 с.)