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

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

Алгоритм задают в виде системы подстановок, реализующих отображение слов pi в слова qi.

pi ® qi=1,…,k.

Порядок подстановок зафиксирован. Объектом i-й элементарной операции алгоритма является слово в алфавите A, операция состоит в нахождении в этом слове первого слева вхождения слова pi и замене его на qi. Результатом операции будет изменённое слова, если вхождение найдено, или входное слово, если не найдено.Факт замены фиксируется и используется в организации следования операций.

Исходное задание представляется некоторым словом в алфавите A. Это слово является входным для первой операции, если замена произошла, то снова выполняется первая операция, если нет, то выполняется следующая операция. После каждой операции выполняется следующая операция, если замена произошла, иначе переходят к выполнению первой операции.

Алгоритм удобно представить в виде ориентированного графа, вершинами которого являются элементарные операторы и распознаватели.

Распознаватель проверяет условие – имеет ли место вхождение рi во входное слово p. Если ДА, то за ним следует оператор, который заменяет первое слева вхождение слова рi на слово qi. Если НЕТ, то управление передается на вход следующего распознавателя.

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

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

На вход графа подается некоторое входное слово p.

Пример. Граф для трех подстановок (к = 3) (рис.1) имеет три распознавателя (РВ1,РВ2,РВ3) и три операторные вершины (ОП1,ОП2,ОП3).

Если подстановки заданы как ba ® ab, bc ® ba, bb ® ac, а входное слово

р = bcbaab, то работа алгоритма будет иметь следующий вид.

Пpимеp. Задан алфавит А={+, 1} и система подстановок:

‘1+1’ ® ‘11’, ‘1’®`1`.

Обычная Заключительная

подстановка подстановка

Пусть дано входное слово р = ’11+11+1’. Оно перерабатывается алгоритмом в строку:

‘11+11+1’ ® ‘1111+1’ ® ‘11111’ ® `11111`!

Алгоритм реализует сложение единиц.