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

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

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

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

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

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

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

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

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

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

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

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

Примеры.