Задача 3. Состояние q1 — уменьшаем младшую (очередную) цифру на 1
Состояние q 1 — уменьшаем младшую (очередную) цифру на 1. Если она не равна нулю, то после уменьшения сразу — останов, если же младшая цифра равна 0, то вместо нее пишем 9, смещаемся влево и вновь выполняем вычитание. В клетку [ a 0, q 1] машина Тьюринга никогда не попадет, поэтому ее можно не заполнять. Задача 4 (усложнение задачи 3)
Состояние q 1 — уменьшаем младшую (очередную) цифру на 1. Если она больше 1, то после уменьшения — сразу останов, если же младшая цифра равна 0, то вместо нее пишем 9, смещаемся влево и вновь выполняем вычитание. Если уменьшаемая цифра равна 1, то вместо нее пишем 0 и переходим в состояние q 2. Состояние q 2 — после записи “0” в каком-либо разряде надо проанализировать, не является ли этот ноль старшей незначащей цифрой (т.е. не стоит ли слева от него в записи выходного слова a 0). Состояние q 3 — если записанный “0” является старшей незначащей цифрой, то его надо удалить из записи выходного слова. Те клетки, в которые машина Тьюринга никогда не попадает, оставляем пустыми.
|
