Нормальные алгоритмы Маркова. Примеры решений
На этой странице вы найдете готовые примеры заданий по построению нормальных алгоритмов.
Типовые задачи снабжены подробным решением, формулами, пояснениями. Используйте их, чтобы научиться решать подобные задачи или закажите решение своей работы нам.
Может пригодиться: Конечные автоматы, машина Тьюринга
Задачи и решения о нормальных алгоритмах
Задача 1. Используя теоремы сочетания, построить НА, аннулирующий все палиндромы в алфавите V. Указание: используйте схемы алгорифмов обращения и правого присоединения слова через разделитель).
Алфавит: $V=\{a,b,c,...,z\}$
Задача 2. Построить НА (нормальный алгоритм) для выполнения сложения и умножения конструктивных натуральных чисел.
Задача 3. С использованием теорем сочетания, построить НА, который аннулирует все слова вида $xx^R$, где $x \in \{a, b\}^*$.
Задача 4. Написать схему НА, обращающего любое слово в заданном алфавите $V$, т.е. перерабатывающего любое слово $w \in V^*$, в слово $w^R$.
Нормальные алгоритмы Маркова
Теория нормальных алгоритмов (или алгорифмов, как называл их создатель теории) была разработана советским математиком А. А. Марковым в конце 1940-х — начале 1950-х гг. Эти алгоритмы представляют собой некоторые правила по переработке слов в алфавите, так что и исходные данные, и результаты работы алгоритмов являются словами в этом алфавите.
Задание нормального алгоритма состоит из 2 этапов: определения алфавита алгоритма (к словам, из символов которого алгоритм будет применяться) и определения его схемы. Схемой нормального алгоритма называется конечный упорядоченный набор так называемых формул подстановки, каждая из которых может быть простой или заключительной.
Нормальные алгоритмы являются вербальными (словесными), то есть предназначенными для применения к словам в различных алфавитах. Как и машины Тьюринга, нормальные алгоритмы не производят собственно вычислений: они лишь производят преобразования слов, заменяя в них одни буквы другими по предписанным им правилам.
