А={0,1,2,3,4,5,6,7,8,9}. Пусть Р – непустое слово; значит, Р – это последовательность из десятичных цифр, т.е. запись неотрицательного целого числа в десятичной системе. Требуется получить на ленте запись числа, которое на 1 больше числа Р.
Решение.
Для решения этой задачи предлагается выполнить следующие действия:
Перегнать автомат под последнюю цифру числа.
Если это цифра от 0 до 8, то заменить её цифрой на 1 больше и остановиться; например:
Если же это цифра 9, тогда заменить её на 0 и сдвинуть автомат к предыдущей цифре, после чего таким же способом увеличить на 1 ту предпоследнюю цифру; например:
Особый случай: в Р только девятки (например, 99). Тогда автомат будет сдвигаться влево, заменяя девятки на нули, и в конце концов окажется под пустой клеткой. В эту пустую клетку надо записать 1 и остановиться (ответом будет 100):
В виде программы для МТ эти действия описываются следующим образом:
Задачи для решения
Замечания:
1) В задачах рассматриваются только целые неотрицательные числа, если не сказано иное.
2) Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек – должно быть выписано столько палочек, какова величина числа; например: 2→ | |, 5 → | | | | |, 0 → <пустое слово>.
1. A={a,b,c}. Приписать слева к слову P символ b (P → bP).
2. A={a,b,c}. Приписать справа к слову P символы bc (P → Pbc).
3. A={a,b,c}. Заменить на a каждый второй символ в слове P.
4. A={a,b,c}. Оставить в слове P только первый символ (пустое слово не менять).
5. A={a,b,c}. Оставить в слове P только последний символ (пустое слово не менять).
6. A={a,b,c}. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или пустое слово иначе.
7. A={a,b,c}. Определить, входит ли в слово P символ a. Ответ: слово из одного символа a (да, входит) или пустое слово (нет).
8. A={a,b,c}. Если в слово P не входит символ a, то заменить в P все символы b на с, иначе в качестве ответа выдать слово из одного символа a.
9. A={a,b,0,1}. Определить, является ли слово P идентификатором (непустым словом, начинающимся с буквы). Ответ: слово a (да) или пустое слово (нет).
10. A={a,b,0,1}. Определить, является ли слово P записью числа в двоичной системе счисления (непустым словом, состоящем только из цифр 0 и 1). Ответ: слово 1 (да) или слово 0.
11. A={0,1}. Считая непустое слово P записью двоичного числа, удалить из него незначащие нули, если такие есть.
12. A={0,1}. Для непустого слова P определить, является ли оно записью степени двойки (1, 2, 4, 8, …) в двоичной системе счисления. Ответ: слово 1 (является) или слово 0.
13. A={0,1,2,3}. Считая непустое слово P записью числа в четверичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0.
14. A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное учетверенному числу P (например: 101 → 10100).
15. A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное неполному частному от деления числа P на 2 (например: 1011 → 101).
16. A={a,b,c}. Если P – слово чётной длины (0, 2, 4, …), то выдать ответ a, иначе – пустое слово.
17. A={0,1,2}. Считая непустое слово P записью числа в троичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0. (Замечание: в чётном троичном числе должно быть чётное количество цифр 1.)
18. A={a,b,c}. Пусть P имеет нечётную длину. Оставить в P только средний символ.
19. A={a,b,c}. Если слово P имеет чётную длину, то оставить в нём только левую половину.
20. A={a,b,c}. Приписать слева к непустому слову P его первый символ.
21. A={a,b}. Для непустого слова P определить, входит ли в него ещё раз его первый символ. Ответ: a (да) или пустое слово.
22. A={a,b}. В непустом слове P поменять местами его первый и последний символы.
23. A={a,b}. Определить, является P палиндромом (перевёртышем, симметричным словом) или нет. Ответ: a (да) или пустое слово.
24. A={a,b}. Заменить в P каждое вхождение a на bb.
25. A={a,b,c}. Заменить в P каждое вхождение ab на c.
26. A={a,b}. Удвоить слово P (например: abb → abbabb).
27. A={a,b}. Удвоить каждый символ слова P (например: bab → bbaabb).
28. A={a,b}. Перевернуть слово P (например: abb → bba).
29. A={0,1}. Считая непустое слово P записью двоичного числа, получить это же число, но в четверичной системе. (Замечание: учесть, что в двоичном числе может быть нечётное количество цифр.)
30. A={0,1,2,3}. Считая непустое слово P записью числа в четверичной системе счисления, получить запись этого числа в двоичной системе.
31. A={0,1,2}. Считая непустое слово P записью положительного числа в троичной системе счисления, уменьшить это число на 1.
32. A={ | }. Считая слово P записью числа в единичной системе счисления, получить запись этого числа в троичной системе. (Рекомендация: следует в цикле удалять из «единичного» числа по палочке и каждый раз прибавлять 1 к троичному числу, которое вначале положить равным 0.)
33. A={0,1,2}. Считая непустое слово P записью числа в троичной системе счисления, получить запись этого числа в единичной системе.
34. Пусть слово P имеет вид ||... | ⊗ ||... |, где ⊗ – один из знаков +, –, ×, /, ÷, ↑ или ↓, слева от которого указано n палочек, а справа – m палочек. Реализовать соответствующую операцию в единичной системе счисления (в качестве ответа выдать слово, указанное справа от стрелки):
а) сложение: ||... | + ||... | →||... |, справа от стрелки n + m палочек (n≥0, m≥0)
б) вычитание: ||... | ‑ ||... | →||... |, справа от стрелки n ‑ m палочек (n≥m≥0)
в) умножение: ||... | × ||... | →||... |, справа от стрелки m × n палочек (n≥0, m≥0)
г) деление нацело: ||... | / ||... | →||... |, справа от стрелки k=n div m палочек (n≥0, m>0)
д) взятие остатка: ||... | ÷ ||... | →||... |, справа от стрелки k=n mod m палочек (n≥0, m>0)
е) максимум: ||... | ↑ ||... | →||... |, справа от стрелки k=max(n,m) палочек (n≥0, m≥0)
ж) минимум: ||... | ↓ ||... | →||... |, справа от стрелки k=min(n,m) палочек (n≥0, m≥0)
35. A={ | }. Считая слово P записью числа в единичной системе, определить, является ли это число степенью 3 (1, 3, 9, 27, …). Ответ: пустое слово, если является, или слово из одной палочки иначе.
36. A={ | }. Считая слово P записью числа n в единичной системе, получить в этой же системе число 2n.
37. A={ | }. Пусть слово P является записью числа 2n (n=0, 1, 2, …) в единичной системе. Получить в этой же системе число n.
38. Пусть P имеет вид Q+R, где Q и R – непустые слова из символов 0, 1 и 2. Трактуя Q и R как записи чисел в троичной системе счисления (возможно, с незначащими нулями), выдать в качестве ответа запись суммы этих чисел в той же троичной системе.
39. Пусть P имеет вид Q–R, где Q и R – непустые слова из символов 0, 1 и 2. Трактуя Q и R как записи чисел в троичной системе счисления (возможно, с незначащими нулями) и считая, что Q≥R, выдать в качестве ответа запись разности этих чисел в той же троичной системе.
40. Пусть P имеет вид Q=R, где Q и R – любые слова из символов a и b. Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе.
41. Пусть P имеет вид Q=R, где Q и R – непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.
42. Пусть P имеет вид Q>R, где Q и R – непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если число Q больше числа R, и слово 0 иначе.
43. A={(,)}. Определить, сбалансировано ли слово P по круглым скобкам. Ответ: Д (да) или Н (нет).
44. A={a,b}. Если в P символов a больше, чем символов b, то выдать ответ a, если символов a меньше символов b, то выдать ответ b, а иначе в качестве ответа выдать пустое слово.
[1] Эмуля́ция (англ. emulation) — воспроизведение программными или аппаратными средствами либо их комбинацией работы других программ или устройств. Эмуляция позволяет выполнять компьютерную программу на платформе (компьютерной архитектуре и/или операционной системе), отличной, или в некоторых случаях идентичной той, для которой она была написана в оригинале. Эмуляцией также называют сам процесс этого выполнения. В отличие от симуляции, которая лишь воспроизводит поведение программы, при эмуляции ставится цель точного моделирования состояния имитируемой системы, для выполнения оригинального машинного кода.
[2]Если надо указать, что после выполнения некоторого такта МТ должна остановиться, то в третьей позиции этого такта будем писать знак «!». Например, такт b,L,! означает следующие действия: запись символа b в видимую клетку ленты, сдвиг влево и останов.