Пример 5 (сжатие слова) А={a,b,c}. Удалить из слова Р первое вхождение символа a, если такое есть.
Решение. В предыдущем примере мы переносили на позицию вправо только один символ. В данном же примере мы будем в цикле переносить вправо все начальные символы b и c входного слова - до первого символа a или до пустой клетки:
Центральный момент здесь - как перенести символ x из левой клетки в очередную клетку, где находится некоторый символ y, чтобы затем этот символ у можно было перенести в правую клетку? Если через qx обозначить состояние, в котором в видимую клетку надо записать символ x, находившийся ранее в клетке слева, тогда это действие можно изобразить так:
Для этого предлагается выполнить такт x,R,qy, в котором объединены следующие три действия: во-первых, в видимую клетку записывается символ x, взятый из клетки слева; во-вторых, автомат сдвигается вправо - под клетку, в которую затем надо будет записать только что замененный символ y; в-третьих, автомат переходит в состояние qy, в котором он и будет выполнять эту запись.
Повторение таких тактов в цикле и приведет к сдвигу вправо на одну позицию начальных символов входного слова. Этот цикл должен закончиться, когда в очередной клетке окажется символ a или Λ (y=a или y=Λ), а в начале цикла можно считать, что на место первого символа слева переносится символ «пусто» (x=Λ). В итоге получается следующая программа для МТ:
В этой программе следует обратить внимание на такт Λ,R,! , который выполняется в конфигурации , т.е. когда первым символом входного слова является a. Ясно, что надо просто стереть этот символ и остановиться. Однако в этом такте указан еще и сдвиг вправо. Зачем? Напомним, что в момент останова автомат должен находиться под выходным словом (под любым его символом), поэтому мы и сдвигаем автомат с пустой клетки на клетку с первым символом выходного слова, который во входном слове был вторым.
Достарыңызбен бөлісу: |
