Задачи для решения
Замечания:
1.В задачах рассматриваются только целые неотрицательные числа, если не сказано иное.
2. Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек - должно быть выписано столько палочек, какова величина числа;
например: 2→| | , 5 → | | | | | , 0 → <пустое слово>.
A={0,1}. Для непустого слова P определить, является ли оно записью степени двойки (1, 2, 4, 8, ...) в двоичной системе счисления. Ответ: слово 1 (является) или слово 0.
A={0,1,2,3}. Считая непустое слово P записью числа в четверичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0.
A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное учетверенному числу P (например: 101 ^ 10100).
A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное неполному частному от деления числа P на 2 (например: 1011 ^ 101).
A={a,b,c}. Если P - слово чётной длины (0, 2, 4, ...), то выдать ответ a, иначе - пустое слово.
A={0,1,2}. Считая непустое слово P записью числа в троичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0. (Замечание: в чётном троичном числе должно быть чётное количество цифр 1.)
A={a,b,c}. Пусть P имеет нечётную длину. Оставить в P только средний символ.
A={a,b,c}. Если слово P имеет чётную длину, то оставить в нём только левую половину.
A={a,b,c}. Приписать слева к непустому слову P его первый символ.
A={a,b}. Для непустого слова P определить, входит ли в него ещё раз его первый символ. Ответ: а (да) или пустое слово.
A={a,b}. В непустом слове P поменять местами его первый и последний символы.
Практическая работа №3: Сжатие слова, вставка символа в слово.
Пример 1 (сжатие слова) А={а,b,с}. Удалить из слова Р первое вхождение символа а, если такое есть.
Решение.
В предыдущем примере мы переносили на позицию вправо только один символ. В данном же примере мы будем в цикле переносить вправо все начальные символы b и c входного слова - до первого символа a или до пустой клетки:
Центральный момент здесь - как перенести символ х из левой клетки в очередную клетку, где находится некоторый символ у, чтобы затем этот символ у можно было перенести в правую клетку? Если через qx обозначить состояние, в котором в видимую клетку надо записать символ х, находившийся ранее в клетке слева, тогда это действие можно изобразить так:
Для этого предлагается выполнить такт x,R,qy, в котором объединены следующие три действия: во-первых, в видимую клетку записывается символ х, взятый из клетки слева; во-вторых, автомат сдвигается вправо - под клетку, в которую затем надо будет записать только что заменённый символ у; в-третьих, автомат переходит в состояние qy, в котором он и будет выполнять эту запись.
Повторение таких тактов в цикле и приведёт к сдвигу вправо на одну позицию начальных символов входного слова. Этот цикл должен закончиться, когда в очередной клетке окажется символ a или Л (y=a или у=Ʌ), а в начале цикла можно считать, что на место первого символа слева переносится символ «пусто» (х=Ʌ). В итоге получается следующая программа для МТ:
В этой программе следует обратить внимание на такт Ʌ,R,! , который выполняется в конфигурации <a, ql>, т.е. когда первым символом входного слова является a. Ясно, что надо просто стереть этот символ и остановиться. Однако в этом такте указан ещё и сдвиг вправо. Зачем? Напомним, что в момент останова автомат должен находиться под выходным словом (под любым его символом), поэтому мы и сдвигаем автомат с пустой клетки на клетку с первым символом выходного слова, который во входном слове был вторым.
Пример 2 (вставка символа в слово) A={a,b,c}. Если Р - непустое слово, то за его первым символом вставить символ a.
Решение.
Ясно, что между первым и вторым символами слова Р надо освободить клетку для нового символа a. Для этого надо перенести на одну позицию влево первый символ (на старом месте его можно пока не удалять), а затем, вернувшись на старое место, записать символ a:
Перенос символа на одну позицию влево аналогичен переносу символа вправо, о чём говорилось в двух предыдущих примерах, поэтому приведем программу для МТ без дополнительных комментариев. Отметим лишь, что в состояниях q2, q3 и q4 автомат может видеть только пустую клетку, а в состоянии q5 он обязательно видит первый символ входного слова, но не пустую клетку.
1.В задачах рассматриваются только целые неотрицательные числа, если не сказано иное.
2. Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек - должно быть выписано столько палочек, какова величина числа;
например: 2→| | , 5 → | | | | | , 0 → <пустое слово>.