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

Автор - А.А. Марков, отдавал предпочтение транскрипции алгори ф м. Нормальные алгорифмы Маркова представляются нормальной схемой подстановок, которая состоит из совокупности подстановок, расположенных в определенном порядке. Подстановки имеют вид: P ® (·) Q (P ® Q – (простая)подстановка, P ® · Q – заключительная подстановка).

Говорят, что строка R входит в строку L, если L имеет вид L₁RL₂.

Говорят, что подстановка применима к слову, если строка, соответствующая левой части подстановки, входит в слово. Применение заключается в замене в преобразуемом слове левой строки подстановки правой.

Две особые подстановки:

P ® - аннулирующая.

® Q - порождающая.

Механизм работы нормальных алгорифмов:

0) Дано (преобразуемое) слово – цепочка символов фиксированного алфавита и нормальная схема подстановок, содержащая фиксированную последовательность простых и заключительных подстановок.

1) Слово всегда просматривается слева направо.

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

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

Примеры.