Практическая работа № 38
«Нормальные алгоритмы Маркова»

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

*0 → 0*
*1 → 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.