Машина Тьюринга


A = a, b . Подвоїти кожен символ слова P (наприклад: bab → bbaabb).

Ответ:

Пошаговое объяснение:

Q1 - смотрим, что за символ. Если пусто, значит все скопировано, выходим.

Q2 - забрали символ a, ползем вправо до конца старого слова.

Q3 - забрали символ b, ползем вправо до конца старого слова.

Q4 - дошли до нового слова, несем символ a, ищем его конец.

Q5 - дошли до нового слова, несем символ b, ищем его конец.

Q6 - нашли конец нового слова, ставим первый символ a.

Q7 - нашли конец нового слова, ставим второй символ b.

Q8 - вовращаемся к началу нового слова.

Q9 - идем к началу оставшейся части старого слова.

Сначала пусть каретка находится на крайнем левом символе слова в состоянии Q1.