Задачи для решения

Замечания:

1.В задачах рассматриваются только целые неотрицательные числа, если не сказано иное.

2. Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек - должно быть выписано столько палочек, какова величина числа;

например: 2→| | , 5 → | | | | | , 0 → <пустое слово>.

1. A={a,b}. Определить, является P палиндромом (перевёртышем, симмет­ричным словом) или нет. Ответ: a (да) или пустое слово.

2. A={a,b}. Заменить в P каждое вхождение a на bb.

3. A={a,b,c}. Заменить в P каждое вхождение ab на с.

4. A={a,b}. Удвоить слово P (например: abb ^ abbabb).

5. A={a,b}. Удвоить каждый символ слова P (например: bab ^ bbaabb).

6. A={a,b}. Перевернуть слово P (например: abb ^ bba).

7. A={0,1}. Считая непустое слово P записью двоичного числа, получить это же число, но в четверичной системе. (Замечание: учесть, что в двоичном числе может быть нечётное количество цифр.)

8. A={0,1,2,3}. Считая непустое слово P записью числа в четверичной системе счисления, получить запись этого числа в двоичной системе.

9. A={0,1,2}. Считая непустое слово P записью положительного числа в троичной системе счисления, уменьшить это число на 1.

10. A={ | }. Считая слово P записью числа в единичной системе счисления, получить запись этого числа в троичной системе. (Рекомендация: следует в цикле удалять из «единичного» числа по палочке и каждый раз прибавлять 1 к троичному числу, которое вначале положить равным 0.)

11. A={0,1,2}. Считая непустое слово P записью числа в троичной системе счисления, получить запись этого числа в единичной системе.

Практическая работа № 4: Раздвижка слова, формирование слова на новом месте, фиксирование места на ленте.

Пример 1 (раздвижка слова) A={a,b,c}. Вставить в слово P символ a за первым вхождением символа с, если такое есть.

Решение.

Просматриваем входное слово слева направо до пустой клетки или до первого символа c. В первом случае c не входит в P, поэтому ничего не делаем. Во втором случае надо освободить место для вставляемого символа a, для чего сдвигаем начало слова P (от первого символа до найденного символа c) на одну позицию влево. При этом осуществляем такой сдвиг справа налево - от символа с к началу слова, раз уж автомат находится под этим символом. Кроме того, чтобы затем не возвращаться к освободившейся позиции, начинаем этот сдвиг с записи a вместо найденного символа c. Поскольку этот циклический сдвиг влево реализуется аналогично циклическому сдвигу вправо из примера 5, то не будем пояснять его, а сразу приведём программу для МТ:

Пример 2 (формирование слова на новом месте) A={a,b,c}. Удалить из P все вхождения символа a.

Решение.

Предыдущие примеры показывают, что в МТ достаточно сложно реали­зуются вставки символов в слова и удаления символов из слов. Поэтому иногда проще не раздвигать или сжимать входное слово, а формировать выходное слово в другом, свободном месте ленты. Именно так мы и поступим при решении данной задачи.

Конкретно предлагается выполнить следующие действия:

1.Выходное слово будем строить справа от входного. Чтобы разграничить эти слова, отделим их некоторым вспомогательным символом, например знаком =, отличным от всех символов алфавита A (см. шаг 1). (Напомним, что на ленте могут быть записаны не только символы из алфавита входного слова.)

2.После этого возвращаемся к началу входного слова (см. шаг 2).

3. Теперь наша задача - перенести в цикле все символы входного слова, кроме а, вправо за знак = в формируемое выходное слово.

Для этого анализируем первый символ входного слова. Если это а, тогда стираем его и переходим к следующему символу (см. шаг 3). Если же первый символ - это b или с, тогда стираем его и «бежим» вправо до первой пустой клетки (см. шаг 4), куда и записываем этот символ (см. шаг 5).

Снова возвращаемся налево к тому символу, который стал первым во входном слове, и повторяем те же самые действия, но уже по отношению к этому символу (см. шаги 6-9).

4. Этот цикл завершается, когда при возврате налево мы увидим в качестве первого символа знак =. Это признак того, что мы полностью просмотрели входное слово и перенесли все его символы, отличные от а, в формируемое справа выходное слово. Надо этот знак стереть, сдвинуться вправо под выходное слово и остановиться (см. шаг 10).

С учётом всего сказанного и строим программу для МТ. При этом отметим, что помимо символов а, b и с в процессе решения задачи на ленте появляется знак =, поэтому в таблице должен быть предусмотрен столбец и для этого знака.

Пример3 (фиксирование места на ленте) А={а,Ь}. Удвоить слово P, поставив между ним и его копией знак.

Например:

Решение.

Эта задача решается аналогично предыдущей: в конец входного слова записываем знак =, затем возвращаемся к началу слова и в цикле все его символы (в том числе и а) копируем в пустые клетки справа:

Однако есть и отличие: копируемые символы входного слова не удаляются, и это приводит к следующей проблеме. Записав справа копию очередного символа, мы затем должны вернуться к входному слову в позицию этого символа и потом сдвинуться вправо к следующему символу, чтобы скопировать уже его. Но как узнать, в какую позицию входного слова надо вернуться? Например, откуда мы знаем в нашем примере, что после копирования первого символа а мы должны вернуться именно к первому символу входного слова, а не ко второму или третьему? В предыдущей задаче мы всегда возвращались к первому из оставшихся символов входного слова, а теперь мы сохраняем все символы, поэтому непонятно, какие символы мы уже скопировали, а какие ещё нет. Отметим также, что в МТ ячейки ленты никак не нумеруются, нет в МТ и счетчиков, которые позволили бы определить, сколько символов мы уже скопировали.

В общем виде проблема, с которой мы столкнулись, следующая: как зафиксировать на ленте некоторую позицию, в которой мы уже были и к которой позже должны вернуться? Обычно эта проблема решается так. Когда мы оказываемся в этой позиции в первый раз, то заменяем находящийся в ней символ на его двойник - на новый вспомогательный символ, причем разные символы заменяем на разные двойники, например а на A и b на B. После этого мы выполняем какие-то действия в других местах ленты. Чтобы затем вернуться к нашей позиции, надо просто отыскать на ленте ту клетку, где находится символ A или B. Затем в данной клетке можно восстановить прежний символ, если нам больше не надо фиксировать эту позицию (именно для восстановления прежнего символа и надо было заменять разные символы на разные двойники).

Воспользуемся этим приёмом в нашей задаче, выполняя следующие действия:

1. Как уже сказано, вначале записываем знак = за входным словом (см. шаг 1 выше).

2. Затем возвращаемся под первый символ входного слова (см. шаг 2 выше).

3. Далее заменяем видимый символ а на двойник A (см. шаг 3 ниже), «бежим» вправо до первой свободной клетки и записываем в неё символ а (см. шаг 4). После этого возвращаемся влево к клетке с двойником A (см. шаг 5), восстанавливаем прежний символ а и сдвигаемся вправо к следующему символу (см. шаг 6).

Теперь аналогичным образом копируем второй символ (заменяем его на A, в конец дописываем а и т.д.) и все последующие символы входного слова.

4. Когда мы скопируем последний символ входного слова и вернёмся к его двойнику (после шага 12), то затем после сдвига на одну позицию вправо мы попадём на знак = (шаг 13). Это сигнал о том, что входное слово полностью скопировано, поэтому работу МТ надо завершать.

С учётом всего сказанного получаем следующую программу для МТ:

Отметим, что в этой программе можно избавиться от состояния q6, если объединить его с состоянием q2, предусмотрев в q2 возврат влево как до пустой клетки, так и до символов A и B: