Решение.

Примеры на составление программ для МТ

Рассмотрим примеры на составление программ для МТ, чтобы продемонстрировать некоторые типичные приёмы программирования на МТ.

Для сокращения формулировки задач введём следующие два соглашения:

– буквой P будем обозначать входное слово;

– буквой A будем обозначать алфавит входного слова, т.е. набор тех символов, из которых и только которых может состоять P (отметим, однако, что в промежуточных и выходном словах могут появляться и другие символы).

Пример 1 (перемещение автомата, замена символов)

А={0,1,2,3,4,5,6,7,8,9}. Пусть P – непустое слово; значит, P – это последовательность из десятичных цифр, т. е. запись неотрицательного целого числа в десятичной системе. Требуется получить на ленте запись числа, которое на 1 больше числа P.

Для решения этой задачи предлагается выполнить следующие действия:

1. Перегнать автомат под последнюю цифру числа.

2. Если это цифра от 0 до 8, то заменить её цифрой на 1 больше и остановиться; например, как показано на рисунке 13.5.

Рисунок 13.5 – Первый и второй шаг выполнения программы

3. Если же это цифра 9, тогда заменить её на 0 и сдвинуть автомат к предыдущей цифре, после чего таким же способом увеличить на 1 эту предпоследнюю цифру, например, как показано на рисунке 13.6.

Рисунок 13.6 – Третий шаг выполнения программы

4. Особый случай: в Р только девятки (например, 99). Тогда автомат будет сдвигаться влево, заменяя девятки на нули, и в конце концов окажется под пустой клеткой. В эту пустую клетку надо записать 1 и остановиться (ответом будет 100), как показано на рисунке 13.7.

Рисунок 13.7 – Четвертый шаг выполнения программы

В виде программы для МТ эти действия описываются следующим образом (рисунок 13.8).

Рисунок 13.8 – Программа для МТ