Лекция 2. Нормальные алгоритмы Маркова. Принцип нормализации и его обоснование. Композиции машин Тьюринга и нормальных алгоритмов Маркова

Элементарные операторы представляют собой алфавитные опе­раторы, предназначенные для реализации алгоритмов в рассмат­риваемой алгоритмической системе.

Элементарные распознаватели служат для распознавания нали­чия тех или иных свойств перерабатываемой алгоритмом инфор­мации и для изменения, в зависимости от результатов распознава­ния, порядка следования элементарных операторов.

Для указания набора элементарных операторов и порядка их следования при задании конкретного алгоритма используют ори­ентированные графы, называемые граф-схемами соответствующих алгоритмов.

Граф-схема алгоритма представляет собой конечное множество соединенных между собой вершин (или геометрических фигур), называемых узлами граф-схемы. Каждому узлу, кроме особых уз­лов, называемых входом и выходом, сопоставляется какой-либо элементарный оператор (ЭО) или элементарный распознаватель (ЭР). При этом из каждого узла, которому сопоставлен оператор, а также из входного узла исходит по одной дуге, а из каждого узла, которому сопоставлен распознаватель, исходит по две дуги. Из вы­ходного узла не исходит ни одной дуги. Число дуг, входящих в узел граф-схемы, может быть любым.

Вариант такой граф-схемы представлен на рис. 1.6. Алгоритм, определенный граф-схемой, работает следующим образом. Вход­ное слово поступает на вход и двигается по направлениям, указан­ным стрелками. При попадании слова в распознавательный узел осуществляется проверка условия, сопоставленного этому узлу. При выполнении условия слово направляется в операторный узел, при невыполнении — к следующему распознавателю.

Если входное слово р, поданное на вход граф-схемы, проходя через узлы схемы и преобразуясь, попадает через конечное число шагов на выход, то считается, что алгоритм применим к слову р (сло­во р входит в область определения этого алгоритма). Результатом воздействия на слово р будет то слово, которое оказывается на вы­ходе схемы. Если после подачи слова р на вход графа его преобра­зование и движение по граф-схеме продолжается бесконечно дол­го, не приводя на выход, считается, что алгоритм не применим к слову р, т.е. слово р не входит в область определения алгоритма.

Рис. 1.6. Вариант граф-схемы алгоритма

Распознаватель вхождения проверяет условие — имеет ли мес­то вхождение рассматриваемого слова р₁ в качестве подслова неко­торого заданного слова q.

Оператор подстановки заменяет первое слева вхождение слова р₁ в слово q на некоторое заданное слово р₂. Оператор подстановки за­дается обычно в виде двух слов, соединенных стрелкой р₁→р₂.

Например, для слова 01230123 применение подстановок  и  через четыре шага приводит к слову 32103210 (рис.1.7):

Рис.1.7. Граф-схема алгоритма преобразования входного слова 01230123 в слово 32103210

Алгоритмы, которые задаются графами, составленными только из распознавателей вхождения слов и операторов подстановки, называют обобщенными нормальными алгоритмами. При этом предполагается, что к каждому оператору подстановки ведет только одна дуга, исходящая из соответствующего распознавателя.

Нормальными алгоритмами называют обобщенные нормальные алгоритмы, граф-схемы которых удовлетворяют следующим усло­виям.

1. Все узлы, соответствующие распознавателям, упорядочиваются путем их нумерации от 1 до n.

Дуги, исходящие из узлов, соответствующих операторам под­становки, подсоединяются либо к узлу, соответствующему перво­му распознавателю, либо к выходному узлу. В первом случае под­становка называется обычной, во втором — заключительной.

Входной узел подсоединяется дугой к первому распознавателю.

Нормальные алгоритмы принято задавать упорядоченным мно­жеством подстановок всех операторов данного алгоритма, назы­ваемым схемой алгоритма. При этом обычные подстановки за­писываются, как и в обобщенных алгоритмах, в виде двух слов, соединенных стрелкой  , а заключительные подстановки обо­значаются стрелкой с точкой  . Процесс выполнения под­становок заканчивается лишь тогда, когда ни одна из подстановок схемы не применима к полученному слову или когда выполнена (первый раз) какая-либо заключительная подстановка.

Вариант граф-схемы нормального алгоритма в общем виде пред­ставлен на рис.1.8.

В качестве примера рассмотрим работу нормального алгоритма А.А. Маркова, алфавит которого представлен алфавитом русского языка, и задано множество подстановок:

1. 
    4. 
   
2. 
    5. 
   
3. 
    6. 
   

Тогда, если на вход подать слово «СЛОН», то оно переработает­ся алгоритмом в выходное слово «МУХА» (рис.1.9):

Новые алгоритмы могут быть построены из уже известных алгоритмов путем суперпозиции, объединения, разветвления алгоритмов и повторения (итерации)

В теории алгоритмов строго доказано, что по своим возможностям преобразования нормальные алгоритмы эквивалентны машине Тьюринга и другим моделям, уточняющим понятие алгоритма.