Справочник от Автор24
Найди эксперта для помощи в учебе
Найти эксперта
+2

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

Определение 1

Нормальные алгоритмы Маркова — это стандартный метод формализованного определения понятия алгоритма.

Теоретические основы нормальных алгоритмов были сформулированы видным математиком Советского Союза А.А. Марковым в конце сороковых годов двадцатого века. Они явились некоторыми базовыми правилами по обработке словесных символов в каких-либо алфавитах, то есть начальными информационными данными и итоговыми результатами таких алгоритмов выступали буквы некоторого алфавита.

Подстановки Маркова

Под алфавитом понимается любые непустые множества. Компоненты алфавита именуются буквами, а все последовательные буквенные наборы считаются словами данного алфавита. При этом могут существовать и пустые слова, то есть не имеющие букв в своём составе. Пустые слова обозначаются символом Ʌ. Если A и B являются двумя алфавитами, и при этом алфавит A принадлежит алфавиту B, то алфавит B выступает как расширение алфавита A. Выполнять обозначение слов принято при помощи латинских букв: P, Q, R. Все слова могут являться составными частями других слов. В этом варианте первое слово считается подсловом второго слова или его вхождением. К примеру, если А является русскоязычным алфавитом, то рассмотрим следующие слова $P_1$= paragraph, $P_2$ = graf, $P_3$ = ra. Слово $P_2$ считается подсловом $P_1$, а $P_3$ это подслово $P_1$ и $P_2$, при этом в $P_1$ присутствует двойное вхождение.

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

Частным случаем подстановок Маркова считаются подстановки с использованием пустых слов:

(Ʌ, Q), (P, Ʌ), (Ʌ, Ʌ).

Ниже в таблице приведены примеры подстановок Маркова, во всех строках которой вначале приведено слово, подлежащее преобразованию, далее применимая к этому слову подстановка Маркова и в конце сформированное в итоге слово:

Примеры подстановок Маркова. Автор24 — интернет-биржа студенческих работ

Рисунок 1. Примеры подстановок Маркова. Автор24 — интернет-биржа студенческих работ

«Нормальные алгоритмы Маркова» 👇
Помощь эксперта по теме работы
Найти эксперта
Решение задач от ИИ за 2 минуты
Решить задачу
Найди решение своей задачи среди 1 000 000 ответов
Найти

Чтобы обозначить Марковскую подстановку (P, Q), применяется запись P → Q. Она носит название формулы подстановки (P, Q). Отдельные подстановки (P, Q) называются заключительными. Чтобы обозначить такие подстановки применяется запись P → Q, которая называется формулой заключительной подстановки. Слово P является левой частью, а слово Q считается правой частью в формуле подстановки.

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

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

P1 → (.)Q1

P2 → (.)Q2

…………….

Pr → (.)Qr.

Данный упорядоченный конечный перечень формул подстановок в алфавите A именуется записью нормального алгоритма в A. Точка, взятая в скобки, показывает, что её в этом месте может и не быть. Приведённая схема даёт определение алгоритма преобразования слов, который называется нормальным алгоритмом Маркова. Сформулируем более точное понимание нормального алгоритма Маркова.

Нормальным алгоритмом Маркова в алфавите А является определённый закон формирования очерёдности слов Vi в алфавите A, на основании заданного слова V в выбранном алфавите. Начальным словом V0 очерёдности слов назначается слово V. Предположим, что некоторого значения i ≥ 0 слово Vi сформировано, и процедура реализации данной последовательности пока не завершена. В случае отсутствия в схеме нормального алгоритма формул, у которых левая часть вошла бы в Vi, то Vi+1 считается равным Vi, что даёт право считать процедуру формирования последовательности завершённой. Но когда в схеме присутствуют формулы, у которых левые части входят в Vi, то за значение Vi+1 принимается итог подстановки Маркова правой части начальной в этих формулах, замещая первое вхождение её левой части в слово. Процедура формирования последовательности может считаться завершённой, когда в текущем шаге использовалась формула финальной подстановки, в противном случае процесс продолжает выполняться. В случае обрыва процедуры формирования упомянутой последовательности, то считается, что текущий нормальный алгоритм можно применить к слову V. Оконечный элемент W последовательности является итогом использования нормального алгоритма к слову V. То есть, по сути, при помощи нормального алгоритма перерабатывается V в W.

Последовательность Vi записывается в таком порядке:

V0 ⇨ V1 ⇨ V2 ⇨ … ⇨ Vm-1 ⇨ Vm.

Здесь V0 = V, а Vm = W.

Это определение является понятием нормального алгоритма в алфавите A. В случае задания алгоритма в каком-либо алфавитном расширении A, то считается, что он является нормальным алгоритмом над A.

Приведём пример нормального алгоритма. Имеется алфавит A = {a, b}. Будем рассматривать такую схему нормального алгоритма в A:

a →. Λ,

b → b.

Задаваемый данной схемой алгоритм работает следующим образом. Любое слово V в алфавите A, которое содержит даже единственное вхождение буквы a, алгоритм переработает в слово, формирующееся из V путём вычёркивания в нём самого первого вхождения символа a. А если слово является пустым, то алгоритм выполняет его переработку также в пустое. Данный алгоритм не может быть использован со словами, содержащими лишь только букву b. К примеру:

aabab ⇨ abab, ab ⇨ b, aa ⇨ a, bbab ⇨ bbb, baba ⇨ bba.

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

Дата написания статьи: 22.06.2020
Найди решение своей задачи среди 1 000 000 ответов
Крупнейшая русскоязычная библиотека студенческих решенных задач
Все самое важное и интересное в Telegram

Все сервисы Справочника в твоем телефоне! Просто напиши Боту, что ты ищешь и он быстро найдет нужную статью, лекцию или пособие для тебя!

Перейти в Telegram Bot