Помогите решить задание с машиной тьюринга

Для циклического сдвига последнего элемента входного слова на одну позицию необходимо выполнить следующие шаги:

Перейти в конец входного слова
Запомнить последний символ
Сдвинуть все символы вправо на одну позицию, начиная со второго с конца
Вставить запомненный символ в начало входного слова
Машина Тьюринга для реализации данного алгоритма может быть построена следующим образом:

Q = {q0, q1, q2, q3, q4, q5}

Σ = {а,б,в,...ю,я, _, $}

Γ = {а,б,в,...ю,я, _, $, X, Y}

q0 - начальное состояние
q1 - переход в конец входного слова
q2 - запомнить последний символ
q3 - сдвиг всех символов вправо на одну позицию, начиная со второго с конца
q4 - вставить запомненный символ в начало входного слова
q5 - конечное состояние

Таблица переходов:

Состояние Входной символ Новый символ Направление Новое состояние
q0 а...ю,я, _ _ -> q1
q1 _ _ <- q2
q2 _ X -> q3
q3 а...ю,я Y -> q3
q3 _ Y <- q4
q4 а...ю,я, Y а...ю,я, Y <- q4
q4 X X -> q0
q5 а...ю,я, X, Y а...ю,я, X -> q5
q5 $ $ -> q5
Начальное состояние - q0
Конечное состояние - q5
Символ _ - пустой символ на ленте
Символ $ - маркер конца входного слова
Символы X, Y - вспомогательные символы на ленте

Для решения данной задачи можно построить машину Тьюринга со следующей конфигурацией:

Q = {q0, q1, q2, q3, q4}
Γ = {а, б, в, ..., ю, я, X}
B = X
q0 = q1
F = {q4}

Описание работы машины Тьюринга:

Начинаем с символа X, который стоит справа от последней буквы в строке.
Считываем последнюю букву в строке и сохраняем ее в память машины.
Перемещаемся налево до тех пор, пока не достигнем символа X.
Заменяем символ X на последнюю букву в строке.
Перемещаемся на одну позицию направо, чтобы остановиться на символе, стоящем справа от последней буквы в строке.
Возвращаемся к началу строки.
Формально, машина Тьюринга может быть описана следующим образом:

(q1, a) -> (q1, a, L) для всех a ∈ A, a ≠ X
(q1, X) -> (q2, X, L)
(q2, a) -> (q2, a, L) для всех a ∈ A
(q2, X) -> (q3, X, L)
(q3, X) -> (q4, X, L)
(q3, a) -> (q0, a, R) для всех a ∈ A, a ≠ X
(q0, X) -> (q4, X, R)

где q0 - состояние, в котором машина возвращает начало строки, q1 - состояние, в котором машина находит символ X, q2 - состояние, в котором машина сохраняет последнюю букву, q3 - состояние, в котором машина возвращается к началу строки, q4 - конечное состояние, в котором машина останавливается.