Надо действительно умножать на два и удалить последнюю цифру.
Умножать можно со старшего разряда, можно с младшего.
Умножение на два алгоритмически достаточно простое и требует небольшого количества состояний.
Нужно определиться с тем что будут означать состояния машины.
Вот, примерная схема, деления на 5, оно же умножения на два со старшего разряда:
Qt - Начало умножения текущей цифры
Qr - На следующем шаге просто пойдём направо
Qrr - Следующие два шага пойдём направо
Ql - Следующий шаг пойдём налево для прибавления единицы
Q1 - Добавление единицы от переполнения на предыдущих шагах
Qlast - Дошли до конца и удаляем последнюю цифру
Qend - Конец
Остальное дело техники - внимательно прописать переходы между состояниями. Вот часть переходов
1 + Qt -> 2 + Qr - на текущей позиции единица, мы вместо неё пишем двойку и готовимся на следующем шаге перейти к следующей цифре.
2 + Qr -> Right + Qt - перешли направо к следующей цифре
6 + Qt -> 2 + Ql - У нас переполнение, поэтому нужно вернуться налево и добавить единичку
2 + Ql -> Left + Q1 - перешли налево для последующего добавления единички
3 + Q1 -> 4 + Qrr - добавили единичку и планируем переместиться на две позиции направо для продолжения работы.
4 + Qrr -> Right + Qr - перемещаемся направо к текущей позиции (остался один переход направо для продолжения алгоритма)
_ + Qt -> Left + Qlast - мы дошли до конца числа - перемещаемся на последнюю цифру для затирания
0 + Qlast -> _ + Qend - затёрли последнюю цифру и заканчиваем работу.
Занимательный факт 1: 9 + Q1 - невозможное состояние
Занимательный факт 2: когда состояние машины Qlast, то она должна указывать на 0.
Простой
Простой
Средний
