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

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

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

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

– буквой 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 – Программа для МТ

Дата добавления: 2013-12-13