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

Алгоритмическая система – это всякий общий способ задания алгоритма.

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

Алгоритм задают в виде граф-схемы - ориентированного графа, вершинами которого являются элементарные операторы и распознаватели. На вход граф - схемы алгоритма (ГСА) подается некоторое входное слово р.

Кроме того, задана система подстановок, реализующих отображение

р_i q_i, i=1,…,k.

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

Например ГСА для трех подставок (К=3) имеет три вершины распознавателя(РВ₁,РВ₂,РВ₃) и три операторные вершины (ОП₁,ОП₂,ОП₃).

Граф имеет два типа

вершин:

а) вершины – распоз -

наватели;

б) операторные вер-

шины;

Кроме того, имеются

входная и выходная

вершины.

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

Из схемы следует, что каждая подстановка р_i q_i, i=1,…,k циклически применяется до тех пор, пока имеются вхождения p_i в p.

После первого применения подстановки p_i q_i, i=1,…,k входное слово p = p⁽¹⁾ преобразуется в слово p⁽¹⁾, после второго применения - в слово p⁽²⁾ и так далее, пока после последнего применения подстановки не преобразуется в выходное слово p⁽⁴⁾ = q .

Алгоритм применим к слову p, если оно преобразуется в слово q через конечное число шагов.

Например, если р=bcbaab, а подстановки заданы как ba ab, bc ba,

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

р=bcbaab bcabab bcaabb baaabb baaaac=q.

Нормальными алгоритмами называются алгоритмы, ГСА которых удовлетворяют следующим условиям:

1. Номера вершин – распознавателей упорядочиваются от 1 до n.

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

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

Рассмотренная выше ГСА для трех подстановок, может быть преобразована в ГСА , соответствующей нормальному алгоритму, например, следующим образом:

р=bcbaab bcabab bcaabb

baaabb abaabb aababb

aaabbb aaaacb.

Для нормального алгоритма преобразование входного слова р=bcbaab в выходное слово q будет иметь следующий вид:

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

‘1+1’ ‘11’ , ‘1’ .

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

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

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

‘11+11+1’ ‘1111+1’ ‘11111’

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

Эквивалентный ему алгоритм можно задать с помощью системы подстановок:

‘+’ Ù, ‘1’

Преобразование слова р в q будет аналогично.

Либо же система подстановок может иметь и такой вид:

‘1+’ ‘+1’ , ‘+1’ ‘1’, ‘1’