Пример 8 (формирование слова на новом месте) А={a,b,c}. Удалить из P все вхождения символа a. Решение

Предыдущие примеры показывают, что в МТ достаточно сложно реали­зуются вставки символов в слова и удаления символов из слов. Поэтому иногда проще не раздвигать или сжимать входное слово, а формировать выходное слово в другом, свободном месте ленты. Именно так мы и поступим при решении данной задачи.

Конкретно предлагается выполнить следующие действия:

1. Выходное слово будем строить справа от входного. Чтобы разграничить эти слова, отделим их некоторым вспомогательным символом, например знаком

2. После этого возвращаемся к началу входного слова (см. шаг 2).

3. Теперь наша задача - перенести в цикле все символы входного слова, кроме a, вправо за знак = в формируемое выходное слово.

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

Снова возвращаемся налево к тому символу, который стал первым во входном слове, и повторяем те же самые действия, но уже по отношению к этому символу (см. шаги 6-9).

4. Этот цикл завершается, когда при возврате налево мы увидим в качестве первого символа знак =. Это признак того, что мы полностью просмотрели входное слово и перенесли все его символы, отличные от a, в формируемое справа выходное слово. Надо этот знак стереть, сдвинуться вправо под выходное слово и остановиться (см. шаг 10).

С учетом всего сказанного и строим программу для МТ. При этом отметим, что помимо символов a, b и c в процессе решения задачи на ленте появляется знак =, поэтому в таблице должен быть предусмотрен столбец и для этого знака.