Пример 6 (вставка символа в слово) А={a,b,c}. Если Р - непустое слово, то за его первым символом вставить символ a.
Решение.
Ясно, что между первым и вторым символами слова Р надо освободить клетку для нового символа a. Для этого надо перенести на одну позицию влево первый символ (на старом месте его можно пока не удалять), а затем, вернувшись на старое место, записать символ a:
Перенос символа на одну позицию влево аналогичен переносу символа вправо, о чем говорилось в двух предыдущих примерах, поэтому приведем программу для МТ без дополнительных комментариев. Отметим лишь, что в состояниях q2, q3 и q4 автомат может видеть только пустую клетку, а в состоянии q5 он обязательно видит первый символ входного слова, но не пустую клетку.
Пример 7 (раздвижка слова)
А={a,b,c}. Вставить в слово P символ a за первым вхождением символа c, если такое есть.
Решение.
Просматриваем входное слово слева направо до пустой клетки или до первого символа c. В первом случае c не входит в P, поэтому ничего не делаем. Во втором случае надо освободить место для вставляемого символа a, для чего сдвигаем начало слова P (от первого символа до найденного символа c) на одну позицию влево. При этом осуществляем такой сдвиг справа налево - от символа с к началу слова, раз уж автомат находится под этим символом. Кроме того, чтобы затем не возвращаться к освободившейся позиции, начинаем этот сдвиг с записи a вместо найденного символа c. Поскольку этот циклический сдвиг влево реализуется аналогично циклическому сдвигу вправо из примера 5, то не будем пояснять его, а сразу приведем программу для МТ:
Достарыңызбен бөлісу: |
