В.Н. Пильщиков, В.Г. Абрамов, А.А. Вылиток, И.В. Горячая - Машина Тьюринга и алгоритмы Маркова. Решение задач (1000390), страница 3
Текст из файла (страница 3)
Отметим лишь, что всостояниях q2, q3 и q4 автомат может видеть только пустую клетку, а в состоянииq5 он обязательно видит первый символ входного слова, но не пустую клетку.q1q2q3q4q5a,L,q2×××, ,!b,L,q3×××a, ,!c,L,q4×××a, ,!Λ, ,!a,R,q5b,R,q5c,R,q5×анализ 1-го символа для переноса его влевоприписать a слеваприписать b слеваприписать c слевазаменить бывший 1-й символ на aПример 7 (раздвижка слова)А={a,b,c}. Вставить в слово P символ a за первым вхождением символа c, еслитакое есть.Решение.Просматриваем входное слово слева направо до пустой клетки или допервого символа c.
В первом случае c не входит в P, поэтому ничего не делаем.Во втором случае надо освободить место для вставляемого символа a, для чегосдвигаем начало слова P (от первого символа до найденного символа c) на однупозицию влево. При этом осуществляем такой сдвиг справа налево – от символаc к началу слова, раз уж автомат находится под этим символом. Кроме того,чтобы затем не возвращаться к освободившейся позиции, начинаем этот сдвиг сзаписи a вместо найденного символа c. Поскольку этот циклический сдвигвлево реализуется аналогично циклическому сдвигу вправо из примера 5, то небудем пояснять его, а сразу приведём программу для МТ:q1q2q3q4a,R,,L,b,L,q2c,L,q2b,R,a,L,q3,L,c,L,q3ca,L,q4a,L,q4b,L,q4,L,Λ,L,!a, ,!b, ,!c, ,!вправо до с, вставка a вместо c, перенос c влевоперенос a справаперенос b справаперенос c справаПример 8 (формирование слова на новом месте)А={a,b,c}.
Удалить из P все вхождения символа a.Решение.Предыдущие примеры показывают, что в МТ достаточно сложно реализуются вставки символов в слова и удаления символов из слов. Поэтому иногдапроще не раздвигать или сжимать входное слово, а формировать выходное сло12во в другом, свободном месте ленты. Именно так мы и поступим при решенииданной задачи.Конкретно предлагается выполнить следующие действия:1. Выходное слово будем строить справа от входного. Чтобы разграничитьэти слова, отделим их некоторым вспомогательным символом, например знаком=, отличным от всех символов алфавита A (см. шаг 1). (Напомним, что на лентемогут быть записаны не только символы из алфавита входного слова.)2.
После этого возвращаемся к началу входного слова (см. шаг 2).a↑bc→1abc→2=↑a↑bc→3=3. Теперь наша задача – перенести в цикле все символы входного слова,кроме a, вправо за знак = в формируемое выходное слово.Для этого анализируем первый символ входного слова. Если это a, тогдастираем его и переходим к следующему символу (см. шаг 3). Если же первыйсимвол – это b или c, тогда стираем его и «бежим» вправо до первой пустойклетки (см. шаг 4), куда и записываем этот символ (см.
шаг 5).→3b↑c=→4c→5=↑c=→6b↑Снова возвращаемся налево к тому символу, который стал первым вовходном слове, и повторяем те же самые действия, но уже по отношению кэтому символу (см. шаги 6-9).→6c↑=b→7=b↑→8=bc↑→94. Этот цикл завершается, когда при возврате налево мы увидим в качествепервого символа знак =. Это признак того, что мы полностью просмотреливходное слово и перенесли все его символы, отличные от a, в формируемоесправа выходное слово. Надо этот знак стереть, сдвинуться вправо подвыходное слово и остановиться (см. шаг 10).→9=↑b→10cb↑cС учётом всего сказанного и строим программу для МТ.
При этомотметим, что помимо символов a, b и c в процессе решения задачи на лентепоявляется знак =, поэтому в таблице должен быть предусмотрен столбец и дляэтого знака.q1q2q3q4q5a,R,,L,Λ ,R,,R,,R,b,R,,L,Λ,R,q4,R,,R,c,R,,L,Λ,R,q5,R,,R,=×,L,Λ,R,!,R,,R,Λ=, ,q2,R,q3×b, ,q2c, ,q213записать справа знак =влево к 1-му символу словаанализ и удаление его, разветвлениезапись b справа, возврат налево (в цикл)запись c справа, возврат налево (в цикл)Пример 9 (фиксирование места на ленте)А={a,b}. Удвоить слово P, поставив между ним и его копией знак =.Например:aa→baab=aabРешение.Эта задача решается аналогично предыдущей: в конец входного словазаписываем знак =, затем возвращаемся к началу слова и в цикле все егосимволы (в том числе и a) копируем в пустые клетки справа:a↑ab→1aab=↑→2a↑ab=→aab=a↑Однако есть и отличие: копируемые символы входного слова не удаляются, иэто приводит к следующей проблеме.
Записав справа копию очередного символа,мы затем должны вернуться к входному слову в позицию этого символа и потомсдвинуться вправо к следующему символу, чтобы скопировать уже его. Но какузнать, в какую позицию входного слова надо вернуться? Например, откуда мызнаем в нашем примере, что после копирования первого символа a мы должнывернуться именно к первому символу входного слова, а не ко второму илитретьему? В предыдущей задаче мы всегда возвращались к первому из оставшихсясимволов входного слова, а теперь мы сохраняем все символы, поэтому непонятно,какие символы мы уже скопировали, а какие ещё нет.
Отметим также, что в МТячейки ленты никак не нумеруются, нет в МТ и счетчиков, которые позволили быопределить, сколько символов мы уже скопировали.В общем виде проблема, с которой мы столкнулись, следующая: какзафиксировать на ленте некоторую позицию, в которой мы уже были и ккоторой позже должны вернуться? Обычно эта проблема решается так.
Когдамы оказываемся в этой позиции в первый раз, то заменяем находящийся в нейсимвол на его двойник – на новый вспомогательный символ, причем разныесимволы заменяем на разные двойники, например a на A и b на B. После этогомы выполняем какие-то действия в других местах ленты. Чтобы затем вернутьсяк нашей позиции, надо просто отыскать на ленте ту клетку, где находитсясимвол A или B. Затем в данной клетке можно восстановить прежний символ,если нам больше не надо фиксировать эту позицию (именно для восстановленияпрежнего символа и надо было заменять разные символы на разные двойники).Воспользуемся этим приёмом в нашей задаче, выполняя следующиедействия:1.
Как уже сказано, вначале записываем знак = за входным словом (см. шаг 1 выше).2. Затем возвращаемся под первый символ входного слова (см. шаг 2 выше).3. Далее заменяем видимый символ a на двойник A (см. шаг 3 ниже), «бежим»вправо до первой свободной клетки и записываем в неё символ a (см. шаг 4). Послеэтого возвращаемся влево к клетке с двойником A (см. шаг 5), восстанавливаемпрежний символ a и сдвигаемся вправо к следующему символу (см. шаг 6).14→2a↑ab→5A↑→7→9…→3=aaA↑b=bb=aaaB↑=→4=→6aA↑→12aa→8aaa↑abA→13Aa=abb=aaab=→5a↑→7→9a↑b=↑aabТеперь аналогичным образом копируем второй символ (заменяем его на A,в конец дописываем a и т.д.) и все последующие символы входного слова.4.
Когда мы скопируем последний символ входного слова и вернёмся к егодвойнику (после шага 12), то затем после сдвига на одну позицию вправо мыпопадём на знак = (шаг 13). Это сигнал о том, что входное слово полностьюскопировано, поэтому работу МТ надо завершать.С учётом всего сказанного получаем следующую программу для МТ:q1q2q3q4q5q6a,R,,L,A,R,q4,R,,R,,L,b,R,,L,B,R,q5,R,,R,,L,=××, ,!,R,,R,,L,A×××××a,R,q3B×××××b,R,q3Λ=,L,q2,R,q3×a, ,q6b, ,q6×поставить = справа от слованалево под 1-й символанализ и замена очередного символазапись a справазапись b справавозврат, восстановление, к след. символуОтметим, что в этой программе можно избавиться от состояния q6, еслиобъединить его с состоянием q2, предусмотрев в q2 возврат влево как до пустойклетки, так и до символов A и B:q2ab,L,,L,=...,L,...ABΛa,R,q3b,R,q3,R,q3налево до Λ, A или B1.3 Задачи для самостоятельного решенияЗамечания:1) В задачах рассматриваются только целые неотрицательные числа, если несказано иное.2) Под «единичной» системой счисления понимается запись неотрицательногоцелого числа с помощью палочек – должно быть выписано столько палочек,какова величина числа; например: 2→ | | , 5 → | | | | | , 0 → <пустое слово>.1.1 A={a,b,c}.
Приписать слева к слову P символ b (P → bP).1.2 A={a,b,c}. Приписать справа к слову P символы bc (P → Pbc).1.3 A={a,b,c}. Заменить на a каждый второй символ в слове P.151.4 A={a,b,c}. Оставить в слове P только первый символ (пустое слово неменять).1.5 A={a,b,c}. Оставить в слове P только последний символ (пустое слово неменять).1.6 A={a,b,c}.
Определить, является ли P словом ab. Ответ (выходное слово):слово ab, если является, или пустое слово иначе.1.7 A={a,b,c}. Определить, входит ли в слово P символ a. Ответ: слово изодного символа a (да, входит) или пустое слово (нет).1.8 A={a,b,c}. Если в слово P не входит символ a, то заменить в P все символыb на с, иначе в качестве ответа выдать слово из одного символа a.1.9 A={a,b,0,1}. Определить, является ли слово P идентификатором (непустымсловом, начинающимся с буквы). Ответ: слово a (да) или пустое слово (нет).1.10 A={a,b,0,1}.
Определить, является ли слово P записью числа в двоичнойсистеме счисления (непустым словом, состоящем только из цифр 0 и 1). Ответ:слово 1 (да) или слово 0.1.11 A={0,1}. Считая непустое слово P записью двоичного числа, удалить изнего незначащие нули, если такие есть.1.12 A={0,1}.
Для непустого слова P определить, является ли оно записьюстепени двойки (1, 2, 4, 8, …) в двоичной системе счисления. Ответ: слово 1(является) или слово 0.1.13 A={0,1,2,3}. Считая непустое слово P записью числа в четверичнойсистеме счисления, определить, является оно чётным числом или нет. Ответ: 1(да) или 0.1.14 A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное учетверенному числу P (например: 101 → 10100).1.15 A={0,1}.
Считая непустое слово P записью числа в двоичной системе,получить двоичное число, равное неполному частному от деления числа P на 2(например: 1011 → 101).1.16 A={a,b,c}. Если P – слово чётной длины (0, 2, 4, …), то выдать ответ a,иначе – пустое слово.1.17 A={0,1,2}. Считая непустое слово P записью числа в троичной системесчисления, определить, является оно чётным числом или нет.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
