ТЕМА 1. НОРМАЛЬНЫЕ  АЛГОРИТМЫ  МАРКОВА
  
             I. Краткие теоретические сведения.
     Нормальные алгоритмы (кратко - н.а.), введенные  сов. математиком
А.А.Марковым, представляют собой класс алгоритмов, применимых к словам
некоторого алфавита. Каждый н.а. определяется указанием алфавита, в кото-
ром он действует, и схемы н.а. Алфавитом н.а. может служить любой конеч-
ный алфавит A. Формулой подстановки в алфавите A называется выражение
типа p->q (простая подстановка) или p=>q (заключительная подстановка),
где p и q - некоторые слова в алфавите A, называемые, соответственно,
левой и правой частями формулы подстановки. Каждый н.а. в алфавите A име-
ет конечное число формул подстановки. Их записывают в виде списка, кото-
рый называется схемой алгоритма.
    Применение н.а. к некоторому слову S заключается в следующем. В спи-
ске формул подстановки ищется первая из тех формул,в которой левая часть
входит в S. Находится 1-е вхождение левой части формулы в S и вместо это-
го вхождения подставляется правая часть формулы.Получается новое слово S'.
Cо словом S' производятся те же действия и т.д.  Данный процесс обрыва-
ется в 2-х случаях: 1) к очередному слову применена одна из заключитель-
ных формул  подстановки; 2) в слово не входит  ни одна  из левых частей
формул  подстановки.  Получаемое  последнее слово  является результатом 
применения н.а. к исходному слову S.
 
         II. Примеры на составление нормальных алгоритмов Маркова.
     Пример 1. В произвольном слове, состоящем из букв {A,B,C} все подряд
стоящие одинаковые буквы заменить одной буквой (например, слово 'ABBBCAA'
преобразовать в 'ABCA').
     Схема н.а. имеет вид: 
     1) AA->A   2) BB->B   3) CC->C
     Применение этой схемы с слову 'ABBBCAA' последовательно даст слова:
'ABBBCA', 'ABBCA' и 'ABCA', после чего выполнение н.а. завершится.
   
     Пример 2. Удвоить слово, состоящее из одинаковых символов (для опре-
деленности - Х). Т.е. слово 'X' надо преобразовать в 'XX', слово 'XX' - в
'XXXX' и т.д.
     Схема н.а. для этого примера намного сложнее, чем для примера 1. 
Нельзя написать 1)Х->XX, т.к. в этом случае на каждом шаге н.а. к слову
будет добавляться символ 'X' и этот процесс будет бесконечным. Введем
дополнительные символы 'Y' и 'Z' и составим схему н.а.:
     1) YX->XY   2) XY->YZZ   3) YZZ->XXZ   4) ZZZ->XXZ    5) XZ=>X  
     6) X->XY
     Эта схема решает поставленную задачу. Применение этой схемы, напри-
мер, к слову 'XX' последовательно даст слова: (6)ХYX, (1)XXY, (2)XYZZ,
(2)YZZZZ, (3)XXZZZ, (4)XXXXZ и (5)XXXX (в скобках указана применяемая
формула подстановки).
  
     III. Описание системы - эмулятора нормальных алгоритмов Маркова.
    Предлагаемая система (автор Новиков М.Д.) позволяет моделировать нор-
мальные алгоритмы Маркова, т.е. с ее помощью можно вводить формулы подста-
новки и выполнять соответствующие преобразования над словами.
    
              Основные команды системы:
    F1 - помощь (выдается список команд и даются пояснения);
    F2 - запись формул подстановки на диск;
    F3 - считывание формул подстановки с диска;
    F4 - ввод преобразуемого слова;
    F5 - выполнение н.а.
    F6 - выполнение н.а. по шагам (после каждой подстановки происходит
         прерывание до нажатия любой клавиши);
    F7 - стирание формул подстановки;
    ALT+X - окончание работы с системой.
 
    Количественные ограничения в системе:
    1) Максимальное количество формул подстановки - 100.
    2) Максимальная длина левых и правых частей формул подстановки - 
       25 символов.
    3) Максимальная длина преобразуемого слова - 255 символов.
  
    Литература.
    1. Энциклопедия кибернетики. - Киев, Полиграфкнига, 1975 г.