Постройте машину Тьюринга, применимую ко всем словам x1x2…xn в алфавите {a, b} и переводящую их в слово α. Запишите программу МТ в виде таблицы.

Введем в алфавит дополнительный символ , ограничивающий входное слово с обеих сторон. Начальная конфигурация МТ обозревает ячейку с крайним левым символом слова.

Примем, что слово не может быть пустым.

Если слово начинается с символа а, то МТ из состояния q1 переходит в состояние q2 и сдвигается вправо, оставляя все символы слова без изменений, до символа , который она стирает, заменяя на символ а, и останавливается.

Если первый символ слова символ b, то МТ из состояния q1 переходит в состояние q3 и сдвигается вправо на одну ячейку. Если второй сим...