Практическая работа. Нормальные алгорифмы Маркова (НАМ)

Практическая работа № 25.   Нормальные алгорифмы Маркова (НАМ)

1.       Что делает следующий НАМ, если применить его к символьной цепочке, состоящей из нулей и единиц:

Ответ:

Как будет работать этот алгоритм при различных начальных состояниях ленты?

Ответ:

2.       Напишите НАМ, который «сортирует» цифры двоичного числа так, чтобы сначала стояли все нули, а потом – все единицы.

Ответ:

3.       Напишите НАМ, который удаляет последний символ строки, состоящей из цифр 0 и 1. Какую операцию он выполняет, если рассматривать строку как двоичную запись числа?

Ответ:

4.       Напишите НАМ, который умножает двоичное число на 2, добавляя 0 в конец записи числа.

Ответ:

5.       Напишите НАМ, который переводит число из двоичной системы счисления в единичную (унарную).

Ответ:

6.       Дано слово, состоящее из букв «а», «б» и пробелов. Постройте нормальный алгоритм Маркова, который символы «а» переносит влево, символы «б» – вправо, а пробелы оставляет посередине.

Ответ:

7.       Дано число в унарной системе счисления (от 1 до 15), сразу после числа стоит точка. Напишите НАМ, который представляет это число в виде суммы степеней двойки (например, для числа 15 нужно получить «8+4+2+1»), и удаляет точку в конце.

Ответ:

8.       *Напишите НАМ, который переводит число из четверичной системы счисления в двоичную. Используйте специальный знак (например, *), который отделяет обработанную часть числа от необработанной.

Ответ:

9.       **Дана последовательность скобок. Напишите НАМ, который проверяет правильность скобочной структуры (парность и вложенность скобок). Например, выражение ()()(())(()())(())() – правильное, а  выражения

()()(())(()())(()))( и ()()(())(()())(())) – неправильные.

Если все правильно, лента должна быть пустой, если выражение неверное, на ленте должны остаться «неправильные» скобки.

10.   **Напишите НАМ, который увеличивает на единицу число, записанное в троичной системе счисления. Используйте специальные символы (например, # и *) для обозначения начала числа и того разряда, который нужно увеличивать первым.

11.   **Напишите НАМ, который уменьшает на единицу число, записанное в троичной системе счисления. Используйте специальные символы (например, # и *) для обозначения начала числа и того разряда, который нужно уменьшать первым.

12.   **Напишите НАМ, который складывает два числа в двоичной системе счисления. Числа разделены знаком «+», например, из строки «1011+1101» нужно получить «11000». Используйте алгоритм, в котором последовательно первое число увеличивается на 1, а второе – уменьшается на 1, пока второе не станет равно 0.