Построить машину Тьюринга, применимую ко всем словам x1x2 ....xn в алфавите {a,b} и переводящую их в слово baba , если слово начинается на ba , x1x2 ....xna  в других случаях.

Машина начинает работу из стандартного состояния, т. е. обозревает ячейку с буквой x_n q₁ начальное состояние, q₀ заключительное состояние, a₀ пустой символ.

Сначала машина должна пройти все слово влево и проверить, начинается ли слово на ba. Если первая буква a, или вторая буква b или пустой символ (слово не начинается на ba), то машина должна пройти все слово вправо, вместо первого пустого символа записать букву a и закончить работу. Если первая буква b, то проверяется вторая буква. Если вторая буква a (слово начинается на ba), то в следующие две ячейки записывается ba, затем машина до...