Учебно-методический комплекс дисциплины для обучающегося «Языки программирования» для специальности 5В010900 Математика

Эта задача решается аналогично предыдущей: в конец входного слова записываем знак =, затем возвращаемся к началу слова и в цикле все его символы (в том числе и a) копируем в пустые клетки справа:

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

В общем виде проблема, с которой мы столкнулись, следующая: как зафиксировать на ленте некоторую позицию, в которой мы уже были и к которой позже должны вернуться? Обычно эта проблема решается так. Когда мы оказываемся в этой позиции в первый раз, то заменяем находящийся в ней символ на его двойник - на новый вспомогательный символ, причем разные символы заменяем на разные двойники, например a на A и b на B. После этого мы выполняем какие-то действия в других местах ленты. Чтобы затем вернуться к нашей позиции, надо просто отыскать на ленте ту клетку, где находится символ A или B. Затем в данной клетке можно восстановить прежний символ, если нам больше не надо фиксировать эту позицию (именно для восстановления прежнего символа и надо было заменять разные символы на разные двойники).

Воспользуемся этим приемом в нашей задаче, выполняя следующие действия:

1. Как уже сказано, вначале записываем знак = за входным словом (см. шаг 1 выше).

2. Затем возвращаемся под первый символ входного слова (см. шаг 2 выше).

3. Далее заменяем видимый символ a на двойник A (см. шаг 3 ниже), «бежим» вправо до первой свободной клетки и записываем в нее символ a (см. шаг 4). После этого возвращаемся влево к клетке с двойником A (см. шаг 5), восстанавливаем прежний символ a и сдвигаемся вправо к следующему символу (см. шаг 6).

Теперь аналогичным образом копируем второй символ (заменяем его на A, в конец дописываем a и т.д.) и все последующие символы входного слова.

4. Когда мы скопируем последний символ входного слова и вернемся к его двойнику (после шага 12), то затем после сдвига на одну позицию вправо мы попадем на знак = (шаг 13). Это сигнал о том, что входное слово полностью скопировано, поэтому работу МТ надо завершать.

С учетом всего сказанного получаем следующую программу для МТ:

Отметим, что в этой программе можно избавиться от состояния q₆, если объединить его с состоянием q₂, предусмотрев в q₂ возврат влево как до пустой клетки, так и до символов A и B: