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

Определение 2.1. Алгоритмом по Маркову (нормальным алгоритмом) называется ассоциативное исчисление с системой ориентированных подстановок, в котором строго оговорено в какой последовательности следует применять эти подстановки.

А именно:

а) система допустимых подстановок задается в определенном порядке (номеруется):

1) P1→ Q1; 2) P2→ Q2; …; n) Pn→ Qn;

номером i (Pi→ Qi), левая часть которой Pi входит в слово R. Если такой подстановки не найдется, то процесс прекращается. В противном случае берется самое левое вхождение Pi в R и оно заменяется Qi. При этом слово R преобразуется в слово R1. Далее, вместо слова R берется слово R1, и процесс начинается сначала. Так поступают до тех пор, пока процесс не прекратится. А это может произойти в двух случаях:

1) К полученному слову Rk не применима ни одна из данных подстановок;

2) Когда при получении слова Rk применена подстановка с меткой, т.е. заключительная подстановка (ее будем метить справа точкой).

При этом считается, что данный алгоритм слово R переработал в слово Rk.

Если процесс переработки слова R ни при каком шаге не обрывается, то говорят, что алгоритм к слову R не применим (результат не определен).

Итак, любое ассоциативное исчисление с упорядоченной системой ориентированных подстановок, которое снабжено описанной выше «инструкций» относительно очередности применения подстановок, задает нормальный алгоритм.

Пример 2.2. Пусть в алфавите A₂ ={a, b, c} задана система ориентированных подстановок:

1. cb → cc

2. cca → ab

3. ab → bca

4. ca → Λ

Этот алгоритм, будучи применен к слову c abc, никогда не обрывается:

- получилось первоначальное слово, т.е. алгоритм закончился.

Если же брать слово baaacca, то после нескольких шагов процесс оборвется на слове bb:

Два нормальных алгоритма отличаются друг от друга алфавитом и системой ориентированных подстановок или даже только порядком подстановок.

Пример 2.3. Пусть в одном и том же алфавите заданы два нормальных алгоритма I1 и I2, отличающиеся друг от друга только порядком подстановок:

I1:

1. ab→ bac
2. ac→ ca
3. aa→ Λ
4. bc → bb
5. bb→ Λ

I2:

1. bc→ bb

2. ab→ bac

3. ac→ ca

4. aa→ Λ

5. bb→ Λ

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