Пример 2 (анализ символов) А={a,b,c}. Перенести первый символ непустого слова Р в его конец. Например: Решение

А={a,b,c}. Перенести первый символ непустого слова Р в его конец. Например:

Запомнить первый символ слова P, а затем стереть этот символ.

Перегнать автомат вправо под первую пустую клетку за P и записать в нее запомненный символ.

Как «бегать» вправо, мы уже знаем из предыдущего примера. А вот как запомнить первый символ? Ведь в МТ нет другого запоминающего устройства, кроме ленты, а запоминать символ в какой-то клетке на ленте бессмысленно: как только автомат сдвинется влево или вправо от этой клетки, он тут же забудет данный символ. Что делать?

Выход здесь таков - надо использовать разные состояния автомата. Если первый символ - это a, то надо перейти в состояние q₂, в котором автомат бежит вправо и записывает в конце a. Если же первым был символ b, тогда надо перейти в состояние q₃, где делается все то же самое, только в конце запи­сывается символ b. Если же первым был символ c, тогда переходим в состояние q₄, в котором автомат дописывает за входным словом символ c. Следовательно, то, каким был первый символ, мы фиксируем переводом автомата в разные состояния. Это типичный прием при программировании на МТ. С учетом сказанного программа будет такой:

Рассмотрим поведение этой программы на входных словах, содержащих не более одного символа. При пустом слове, которое является «плохим» для задачи, программа зациклится - автомат, находясь в состоянии q1 и попадая все время на пустые клетки, будет бесконечно перемещаться вправо. (Конечно, в этом случае программу можно было бы остановить, но мы специально сделали зацикливание, чтобы продемонстрировать такую возможность.)

Если же во входном слове ровно один символ, тогда автомат сотрет этот символ, сдвинется на одну клетку вправо и запишет в нее данный символ:

Таким образом, слово из одного символа попросту сдвинется на клетку вправо. Это допустимо. Ведь клетки ленты не нумерованы, поэтому местоположение слова на ленте никак не фиксируется и перемещение слова влево или вправо заметить нельзя. В связи с этим не требуется, чтобы выходное слово обязательно находилось в том же месте, где было входное слово, результат может оказаться и левее, и правее этого места.

А={a,b,c}. Если первый и последний символы (непустого) слова Р одинаковы, тогда это слово не менять, а иначе заменить его на пустое слово.

• 
  Запомнить первый символ входного слова, не стирая его.
  
• 
  Переместить автомат под последний символ и сравнить его с запомненным. Если они равны, то больше ничего не делать.
  
• 
  В противном случае уничтожить все входное слово.
  

Эти действия описываются следующей программой для МТ (напомним, что крестик в ячейке таблицы означает невозможность появления соответствующей конфигурации при выполнении программы):