В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая - Машина Тьюринга и алгоритмы Маркова. Решение задач, страница 2

Перегнать автомат под последнюю цифру числа.2. Если это цифра от 0 до 8, то заменить её цифрой на 1 больше иостановиться; например:1↑95→7195→7↑1958↑3. Если же это цифра 9, тогда заменить её на 0 и сдвинуть автомат кпредыдущей цифре, после чего таким же способом увеличить на 1 этупредпоследнюю цифру; например:6↑49→649↑→64↑→065↑04. Особый случай: в Р только девятки (например, 99).

Тогда автомат будетсдвигаться влево, заменяя девятки на нули, и в конце концов окажется под пустойклеткой. В эту пустую клетку надо записать 1 и остановиться (ответом будет 100):9↑9→99↑→9↑0→00→↑1↑00В виде программы для МТ эти действия описываются следующим образом:q1q200,R,q11,N,!11,R,q12, N,!22,R,q13, N,!33,R,q14, N,!44,R,q15, N,!55,R,q16, N,!66,R,q17, N,!77,R,q18, N,!88,R,q19, N,!99,R,q10,L,q2ΛΛ,L,q21,N,!Пояснения.q1 – это состояние, в котором автомат «бежит» под последнюю цифру числа.Для этого он всё время движется вправо, не меняя видимые цифры и оставаясь втом же состоянии. Но здесь есть одна особенность: когда автомат находится под7последней цифрой, то он ещё не знает об этом (ведь он не видит, что записано всоседних клетках) и определит это лишь тогда, когда попадёт на пустую клетку.Поэтому, дойдя до первой пустой клетки, автомат возвращается назад под последнюю цифру и переходит в состояние q2 (вправо двигаться уже не надо).q2 – это состояние, в котором автомат прибавляет 1 к той цифре, которуювидит в данный момент.

Сначала это последняя цифра числа; если она – в диапазонеот 0 до 8, то автомат заменяет её цифрой, которая на 1 больше, и останавливается. Ноесли это цифра 9, то автомат заменяет её на 0 и сдвигается влево, оставаясь всостоянии q2. Тем самым, он будет теперь прибавлять 1 к предыдущей цифре. Еслии эта цифра равна 9, то автомат заменяет её на 0 и сдвигается влево, оставаясь попрежнему в состоянии q2, т.к. должен выполнить то же самое действие – увеличитьна 1 видимую цифру. Если же автомат сдвинулся влево, а в видимой клетке нетцифры (а есть «пусто»), то он записывает сюда 1 и останавливается.Отметим, что для пустого входного слова наша задача не определена,поэтому на этом слове МТ может вести себя как угодно.

В нашей программе,например, при пустом входном слове МТ останавливается и выдает ответ 1.Выше мы привели запись программы в полном, несокращённом виде.Теперь же приведём запись программы в сокращённом, более наглядном виде,при этом справа дадим краткое пояснение действий, которые реализуются всоответствующих состояниях автомата:q10,R,1,R,2,R,3,R,4,R,5,R,6,R,7,R,8,R,9,R,Λ,L,q2под последнюю цифруq21, ,!2, ,!3, ,!4, ,!5, ,!6, ,!7, ,!8, ,!9, ,!0,L,1, ,!видимая цифра + 1Именно так мы и будем в дальнейшем записывать программы.Пример 2 (анализ символов)А={a,b,c}. Перенести первый символ непустого слова Р в его конец.Например:abcb→bcbaРешение.Для решения этой задачи предлагается выполнить следующие действия:1.

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

Еслипервый символ – это a, то надо перейти в состояние q2, в котором автомат8бежит вправо и записывает в конце a. Если же первым был символ b, тогда надоперейти в состояние q3, где делается всё то же самое, только в конце записывается символ b. Если же первым был символ c, тогда переходим в состояниеq4, в котором автомат дописывает за входным словом символ c. Следовательно,то, каким был первый символ, мы фиксируем переводом автомата в разныесостояния.

Это типичный приём при программировании на МТ.С учётом сказанного программа будет такой:q1q2q3q4aΛ,R,q2,R,,R,,R,bΛ,R,q3,R,,R,,R,cΛ,R,q4,R,,R,,R,Λ,R,a, ,!b, ,!c, ,!анализ 1-го символа, удаление его, разветвлениезапись a справазапись b справазапись c справаРассмотрим поведение этой программы на входных словах, содержащихне более одного символа. При пустом слове, которое является «плохим» длязадачи, программа зациклится – автомат, находясь в состоянии q1 и попадая всёвремя на пустые клетки, будет бесконечно перемещаться вправо.

(Конечно, вэтом случае программу можно было бы остановить, но мы специально сделализацикливание, чтобы продемонстрировать такую возможность.)Если же во входном слове ровно один символ, тогда автомат сотрёт этотсимвол, сдвинется на одну клетку вправо и запишет в неё данный символ:c↑q1→→↑q4c↑!Таким образом, слово из одного символа попросту сдвинется на клетку вправо.Это допустимо. Ведь клетки ленты не нумерованы, поэтому местоположениеслова на ленте никак не фиксируется и перемещение слова влево или вправозаметить нельзя. В связи с этим не требуется, чтобы выходное словообязательно находилось в том же месте, где было входное слово, результатможет оказаться и левее, и правее этого места.Пример 3 (сравнение символов, стирание слова)А={a,b,c}.

Если первый и последний символы (непустого) слова Р одинаковы,тогда это слово не менять, а иначе заменить его на пустое слово.Решение.Для решения этой задачи предлагается выполнить следующие действия:1. Запомнить первый символ входного слова, не стирая его.2. Переместить автомат под последний символ и сравнить его с запомненным.Если они равны, то больше ничего не делать.3. В противном случае уничтожить всё входное слово.Как запоминать символ и как перегонять автомат под последний символ слова,мы уже знаем из предыдущих примеров. Стирание же входного слова реализуется9заменой всех его символов на символ Λ. При этом, раз уж автомат оказался в концеслова, будем перемещать автомат справа налево до первой пустой клетки.Эти действия описываются следующей программой для МТ (напомним,что крестик в ячейке таблицы означает невозможность появлениясоответствующей конфигурации при выполнении программы):q1q2q3q4q5q6q7q8a, ,q2,R,, ,!,R,, , q8,R,, , q8Λ,L,b, ,q4,R,, , q8,R,, ,!,R,, , q8Λ,L,c, ,q6,R,, , q8,R,, , q8,R,, ,!Λ,L,Λ, ,!, L,q3×, L,q5×, L,q7×, ,!анализ 1-го символа, разветвлениеидти к последнему символу при 1-м символе aсравнить посл.

символ с a, не равны – на q8 (стереть P)аналогично при 1-м символе bаналогично при 1-м символе cстереть всё слово, двигаясь справа налевоПример 4 (удаление символа из слова)А={a,b}. Удалить из слова Р его второй символ, если такой есть.Решение.Казалось бы, эту задачу решить просто: надо сдвинуть автомат подклетку со вторым символом и затем очистить эту клетку:a↑bba→ab↑ba→aba↑Однако напомним, что внутри выходного слова не должно быть пустых клеток.Поэтому после удаления второго символа надо «сжать» слово, перенеся первыйсимвол на одну клетку вправо. Для этого автомат должен вернуться к первомусимволу, запомнить его и стереть, а затем, снова сдвинувшись вправо, записатьего в клетку, где был второй символ. Однако начальный «поход» вправо ковторому символу, чтобы его стереть, и последующий возврат к первомусимволу являются лишними действиями: какая разница – переносить первыйсимвол в пустую клетку или в клетку с каким-то символом? Поэтому сразузапоминаем первый символ, стираем его и записываем вместо второго символа:a↑bba→b↑ba→a↑baВ виде программы для МТ всё это записывается так:q1q2q3aΛ,R,q2,,!b, ,!bΛ,R,q3a, ,!,,!Λ, ,!a, ,!b, ,!анализ и удаление 1-го символа, разветвлениезамена 2-го символа на aзамена 2-го символа на bПример 5 (сжатие слова)А={a,b,c}.

Удалить из слова Р первое вхождение символа a, если такое есть.Решение.В предыдущем примере мы переносили на позицию вправо только один сим10вол. В данном же примере мы будем в цикле переносить вправо все начальныесимволы b и c входного слова – до первого символа a или до пустой клетки:bb↑bccbaa→b↑ba→abca↑a→bcb↑aЦентральный момент здесь – как перенести символ x из левой клетки вочередную клетку, где находится некоторый символ y, чтобы затем этот символy можно было перенести в правую клетку? Если через qx обозначить состояние,в котором в видимую клетку надо записать символ x, находившийся ранее вклетке слева, тогда это действие можно изобразить так:x…yyz…→…xz↑↑qxqy…Для этого предлагается выполнить такт x,R,qy , в котором объединены следующие три действия: во-первых, в видимую клетку записывается символ x,взятый из клетки слева; во-вторых, автомат сдвигается вправо – под клетку, вкоторую затем надо будет записать только что заменённый символ y; в-третьих,автомат переходит в состояние qy, в котором он и будет выполнять эту запись.Повторение таких тактов в цикле и приведёт к сдвигу вправо на однупозицию начальных символов входного слова.

Этот цикл должен закончиться,когда в очередной клетке окажется символ a или Λ (y=a или y=Λ), а в началецикла можно считать, что на место первого символа слева переносится символ«пусто» (x=Λ). В итоге получается следующая программа для МТ:q1q2q3aΛ,R,!b, ,!c, ,!bΛ,R,q2,R,c,R,q2cΛ,R,q3b,R,q3,R,Λ, ,!b, ,!c, ,!qΛ: стереть 1-й символ и перенести его вправоqb: запись b, перенос ранее видимого символа вправоqc: запись c, перенос ранее видимого символа вправоВ этой программе следует обратить внимание на такт Λ,R,! , которыйвыполняется в конфигурации <a, q1>, т.е. когда первым символом входногослова является a. Ясно, что надо просто стереть этот символ и остановиться.Однако в этом такте указан ещё и сдвиг вправо.

Зачем? Напомним, что в моментостанова автомат должен находиться под выходным словом (под любым егосимволом), поэтому мы и сдвигаем автомат с пустой клетки на клетку с первымсимволом выходного слова, который во входном слове был вторым.Пример 6 (вставка символа в слово)А={a,b,c}. Если Р – непустое слово, то за его первым символом вставить символ a.Решение.Ясно, что между первым и вторым символами слова Р надо освободитьклетку для нового символа a.

Для этого надо перенести на одну позицию влево11первый символ (на старом месте его можно пока не удалять), а затем,вернувшись на старое место, записать символ a:b c a↑→b c a→↑bb c↑a→b a c a↑Перенос символа на одну позицию влево аналогичен переносу символавправо, о чём говорилось в двух предыдущих примерах, поэтому приведемпрограмму для МТ без дополнительных комментариев.