3.3.4. Нормальные алгоритмы Маркова
Кратко обсудим третий подход к уточнению (конкретизации) понятия алгоритма. Алгоритм задается системой подстановок, которые указывают, какие замены символов необходимо производить и в каком порядке эти подстановки должны следовать. Такой подход был предложен А.А.Марковым. В начале 50-х годов было введено понятие нормального алгоритма (сам Марков называл их алгорифмами).
Вновь рассмотрим некоторый алфавит A, содержащий конечное число знаков (букв). Введем ряд определений:
Слово – это любая конечная последовательность знаков алфавита. Число символов в слове называется его длиной. Слово, длина которого равна нулю, называется пустым. Слово s называется подсловом слова q, если q можно представить в виде q=rst, где r и t – любые слова в том же алфавите (в том числе и пустые).
Теперь можно определить понятие алгоритма (не являющееся строгим):
Алгоритмом в алфавите A называется эффективно вычислимая функция, областью определения которой служит какое-либо подмножество множества всех слов в алфавите A и значениями которой также являются слова в алфавите A.
В алгоритмах Маркова в качестве элементарного шага алгоритма принимается подстановка одного слова вместо другого. Пусть в алфавите A построено исходное слово P, которое содержит подслово Pr (в общем случае таких подслов в исходном слове может быть несколько), а также имеется некоторое слово Pk в том же алфавите.
Подстановкой называется замена первого по порядку подслова Pr исходного слова P на слово Pk. Обозначается подстановка PrPk.
Алгоритм в данной форме представления задается системой подстановок, которая представляет собой последовательность (список) подстановок. Если в этом списке имеются подстановки с левыми частями, которые входят в P, то первая из них применяется к P, в результате чего оно переходит в другое слово P1. К нему вновь применяется схема подстановок и т.д. Процесс прекращается в двух случаях: либо в списке не нашлось подстановки с левой частью, входящей в Pn, либо при получении Pn была применена последняя подстановка.
Пример 3.8. Пусть задан алфавит A ={ *,1} и единственная подстановка: *11; Найти результат обработки, если исходным является слово P = 11*111*1.
Применение нормального алгоритма с указанной подстановкой к данному слову дает последовательность (подчеркиванием выделяется преобразуемая комбинация): 11*111*1 11111*1 111111, т.е. алгоритм находит количество единиц в исходном слове (суммирует числа в унарной системе счисления).
Пример 3.9. Алфавит содержит символы русского языка: A ={а,б…я}. Найти систему подстановок, обеспечивающих преобразования: путь муть, поломала. Найти результат применения такого алгоритма к исходным словам папа, пузо.
Система подстановок достаточно очевидна: п м, оа.
Применение алгоритма: папа мапа мамапузо музо муза
Пример 3.10. Составить нормальный алгоритм, обеспечивающий выполнение операции сложения в троичной системе счисления.
Алфавит будет содержать символы: A ={0,1,2,+}; система подстановок: 0+11, 1+12, 2+1+10, +11. Применим алгоритм для различных исходных слов:
112+1 11+10 120
22+1 2+10 +100 100
Различные нормальные алгоритмы отличаются друг от друга алфавитами и системами допустимых подстановок. Нормальный алгоритм Маркова можно рассматривать как стандартную форму для задания любого алгоритма. Данная форма представления алгоритма важна не только с точки зрения проведения исследований в теории алгоритмов, но она послужила основой специализированного языка символьных преобразований в системах искусственного интеллекта.