Нормальные алгоритмы Маркова — это стандартный метод формализованного определения понятия алгоритма.
Теоретические основы нормальных алгоритмов были сформулированы видным математиком Советского Союза А.А. Марковым в конце сороковых годов двадцатого века. Они явились некоторыми базовыми правилами по обработке словесных символов в каких-либо алфавитах, то есть начальными информационными данными и итоговыми результатами таких алгоритмов выступали буквы некоторого алфавита.
Подстановки Маркова
Под алфавитом понимается любые непустые множества. Компоненты алфавита именуются буквами, а все последовательные буквенные наборы считаются словами данного алфавита. При этом могут существовать и пустые слова, то есть не имеющие букв в своём составе. Пустые слова обозначаются символом Ʌ. Если 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, Ʌ), (Ʌ, Ʌ).
Ниже в таблице приведены примеры подстановок Маркова, во всех строках которой вначале приведено слово, подлежащее преобразованию, далее применимая к этому слову подстановка Маркова и в конце сформированное в итоге слово:
Рисунок 1. Примеры подстановок Маркова. Автор24 — интернет-биржа студенческих работ
Чтобы обозначить Марковскую подстановку (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.
Аналогично машине Тьюринга, нормальные алгоритмы, по сути, не выполняют отдельных вычислительных операций. Они только осуществляют операции по преобразованию слов, путём замены в них одних букв на другие согласно заложенным в алгоритмы правилам.
