Специальная математика. Соловьев А.Е. - 68 стр.

совокупности подстановок, расположенных в определенном порядке. Подстановки имеют
вид: P  ()Q (P  Q – (простая) подстановка, P  Q – заключительная подстановка).
Говорят, что строка R входит в строку L, если L имеет вид L1RL2.
Говорят, что подстановка применима к слову, если строка, соответствующая левой части
подстановки, входит в слово. Применение заключается в замене в преобразуемом слове
левой строки подстановки правой.
Две особые подстановки:
P  - аннулирующая.
  Q - порождающая.

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

Примеры.
нормальная схема         преобразуемое
подстановок              слово

 xx  y                    xxxyyyzzz
 xy  x                    yxyyyzzz
 yzy  x                   yxyyzzz
 zz . z                   yxyzzz
 yy  x                    yxzzz
                           yxzz

                           МУХА
ХК                        МУКА
МР                        РУКА
КА  ЛОН                   РУЛОН
РУ  СЛ .                  СЛОН

Примеры алгорифмов, использующие           специальные   символы,   аннулирующие   и
порождающие подстановки:
Удвоение исходной строки
х  хх
у  уу
хх  хх
ху  ух
ух  ху
уу  уу

  .
                                         — 68 —