Напишите программу, позволяющую автоматически реализовать нормальный алгоритм Маркова, обрабатывающий входное слово с помощью системы подстановок. Например, дано слово из алфавита {a,b,c,d}, следует расположить буквы в алфавитном порядке.

Нормальная система подстановок осуществляется так: сначала выполняется первая подстановка (x[1] заменяется на y[1]), слово переписывается. Затем - снова первая подстановка; если невозможно - вторая; если вторая не проходит, то третья. Слово переписывается. Снова первая подстановка, если невозможно - вторая; если невозможно - третья. Слово переписывается. Система подстановок, позволяющая расположить буквы в алфавитном порядка, представлена ниже:

slovo:='dabadbcadcbd';
------------
x[1]:='ba';  y[1]:='ab';
x[2]:='ca';  y[2]:='ac';
x[3]:='da';  y[3]:='ad';
x[4]:='cb';  y[4]:='bc';
x[5]:='db';  y[5]:='bd';
x[6]:='dc';  y[6]:='cd';

Для автоматического выполнения нормальногой алгоритм Маркова используется программа ПР-1. Результат работы программы - на рис. 1.

Дана последовательность скобок. С помощью нормальной системы подстановок Маркова определите правильность скобочной структуры.

Чтобы реализовать нормальную систему подстановок Маркова, в программу ПР-1 следует вставить код:

slovo:='()()(())(()())(())';
--------------
x[1]:='**';   y[1]:='*';
x[2]:='()*';  y[2]:='*';
x[3]:='*()';  y[3]:='*';
x[4]:='(*)';  y[4]:='*';
x[5]:='()';  y[5]:='*';

Результат исполнения программы представлен на рис. 2.

Напишите программу, автоматически реализующую нормальный алгоритм Маркова, переводящий число из двоичной системы счисления в унарную.

Чтобы решить эту задачу, в программу ПР-1 следует вставить код:

slovo:='10011';
----------
x[1]:='|0'; y[1]:='0||';
x[2]:='1';  y[2]:='0|';
x[3]:='0|';  y[3]:='|';

Результат решения задачи -- на рис. 3.

Напишите программу, автоматически реализующую нормальный алгоритм Маркова, складывающий два числа.

В программу ПР-1 следует вставить код:

slovo:='8eight+5five';
-------------
x[1]:='1one'; y[1]:='|';
x[2]:='2two'; y[2]:='||';
x[3]:='3three'; y[3]:='|||';
x[4]:='4four'; y[4]:='||||';
x[5]:='5five'; y[5]:='|||||';
x[6]:='6six'; y[6]:='||||||';
x[7]:='7seven'; y[7]:='|||||||';
x[8]:='8eight'; y[8]:='||||||||';
x[9]:='9nine'; y[9]:='|||||||||';
x[10]:='|+|'; y[10]:='||';
x[11]:='||||||||||'; y[11]:='10';
x[12]:='0|||||||||'; y[12]:='9';
x[13]:='0||||||||'; y[13]:='8';
x[14]:='0|||||||'; y[14]:='7';
x[15]:='0||||||'; y[15]:='6';
x[16]:='0|||||'; y[16]:='5';
x[17]:='0||||'; y[17]:='4';
x[18]:='0|||'; y[18]:='3';
x[19]:='0||'; y[19]:='2';
x[20]:='0|'; y[20]:='1';
x[21]:='|||||||||'; y[21]:='9';
x[22]:='||||||||'; y[22]:='8';
x[23]:='|||||||'; y[23]:='7';
x[24]:='||||||'; y[24]:='6';
x[25]:='|||||'; y[25]:='5';
x[26]:='||||'; y[26]:='4';
x[27]:='|||'; y[27]:='3';
x[28]:='||'; y[28]:='2';
x[29]:='|'; y[29]:='1';

Результат решения задачи - на рис. 4.

Напишите программу, автоматически реализующий нормальный алгоритм Маркова, умножающий два числа.

В программу ПР-1 следует вставить код:

slovo:='1111*111';
----------
x[1]:='*11'; y[1]:='A*1';
x[2]:='*1'; y[2]:='A';
x[3]:='1A'; y[3]:='A1B';
x[4]:='BA'; y[4]:='AB';
x[5]:='B1'; y[5]:='1B';
x[6]:='A1'; y[6]:='A';
x[7]:='AB'; y[7]:='B';
x[8]:='B'; y[8]:='1';

Результат работы программы - на рис. 5. Другой пример решения задачи:

slovo:='1111*111';
-----------
x[1]:='1*'; y[1]:='X';
x[2]:='_1'; y[2]:='1_Z';
x[3]:='Z1'; y[3]:='1Z';
x[4]:='1X'; y[4]:='X_';
x[5]:='X'; y[5]:='';
x[6]:='_'; y[6]:='';
x[7]:='Z'; y[7]:='1';

Имеется число в четверичной системе счисления. Предложите систему нормальных подстановок, которая переводит это число в двоичную систему счисления. Апробируйте решение на компьютере.

В программу ПР-1 следует вставить код:

slovo:='*3021032';
------------
x[1]:='*0';  y[1]:='00*';
x[2]:='*1';  y[2]:='01*';
x[3]:='*2';  y[3]:='10*';
x[4]:='*3';  y[4]:='11*';
x[5]:='*';   y[5]:=' ';

Дано двоичное число. Предложите систему нормальных подстановок, которая инвертирует все 0 и 1. Апробируйте решение на компьютере.

В программу ПР-1 следует вставить код:

slovo:='*011010101';
-----------
x[1]:='*0';  y[1]:='1*';
x[2]:='*1';  y[2]:='0*';
x[3]:='*';   y[3]:=' ';

Дано число в унарной системе счисления от 1 до 15. Предложите систему нормальных подстановок, которая представляет его как сумму степеней числа 2. Апробируйте решение на компьютере.

В программу ПР-1 следует вставить код:

slovo:='|||||||||||||_';
-------------
x[1]:='||||||||';   y[1]:='8+';
x[2]:='||||';       y[2]:='4+';
x[3]:='||';         y[3]:='2+';
x[4]:='|';          y[4]:='1+';
x[5]:='+_';         y[5]:=' ';

Имеется слово 'BAB_BA_AA_BABB_ABA'. Создайте нормальный алгоритм Маркова, который символы 'A' переносит влево, символы 'B' - вправо, а пробелы оставляет посередине. Промоделируйте на компьютере. (Ответ: 1) 'BA' => 'AB'; 2) 'B_' => '_B'; 3) '_A' => 'A_').