Задачи для самостоятельного решения по автомату Тьюринга.
Замечания:
В задачах рассматриваются только целые неотрицательные числа.
Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек - должно быть выписано столько палочек, какова величина числа; например: 2→ | | , 5 → | | | | | , 0 → <пустое слово>.
1.A={a,b}. Для непустого слова Р определить, входит ли в него ещё раз его первый символ. Ответ: а (да) или пустое слово.
2.A={a,b}. В непустом слове Р поменять местами его первый и последний символы.
3.A={a,b}. Заменить в Р каждое вхождение а на bb.
4. A={a,b}. Перевернуть слово P (например: abb → bba).
5.A={a,b,c}. Заменить в Р каждое вхождение ab на с.
6.A={a,b,c}. Заменить на а каждый второй символ в слове Р.
7. A={a,b,c}. Оставить в слове P только первый символ (пустое слово не менять).
8. A={a,b}. Пусть слово Р имеет нечётную длину. Удалить из него средний символ.
9. A={a,b,c}. Оставить в слове P только последний символ (пустое слово не менять).
10. A={a,b,c}. Определить, является ли P словом ab. Ответ (выходное слово): слово ab, если является, или пустое слово иначе.
11. A={a,b,c}. Пусть P имеет нечётную длину. Оставить в P только средний символ.
12. A={a,b,c}. Определить, входит ли в слово P символ a. Ответ: слово из одного символа a (да, входит) или пустое слово (нет).
13. A={a,b,c}. Если в слово P не входит символ a, то заменить в P все символы b на с, иначе в качестве ответа выдать слово из одного символа a.
14. A={a,b,0,1}. Определить, является ли слово P идентификатором (непустым словом, начинающимся с буквы). Ответ: слово a (да) или пустое слово (нет).
|
|
|
15. A={a,b,0,1}. Определить, является ли слово P записью числа в двоичной системе счисления (непустым словом, состоящем только из цифр 0 и 1). Ответ: слово 1 (да) или слово 0.
16. A={0,1}. Считая непустое слово P записью двоичного числа, удалить из него незначащие нули, если такие есть.
17. A={0,1}. Для непустого слова P определить, является ли оно записью степени двойки (1, 2, 4, 8, в двоичной системе счисления. Ответ: слово 1 (является) или слово 0.
18. A={0,1,2,3}. Считая непустое слово P записью числа в четверичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0.
19. A={0,1}. Считая непустое слово P записью числа в двоичной системе, получить двоичное число, равное учетверенному числу P (например: 101 → 10100).
20. A={a,b,c}. Если P - слово чётной длины (0, 2, 4,…), то выдать ответ a, иначе - пустое слово.
21. A={0,1,2}. Считая непустое слово P записью числа в троичной системе счисления, определить, является оно чётным числом или нет. Ответ: 1 (да) или 0. (Замечание: в чётном троичном числе должно быть чётное количество цифр 1.)
22. A={a,b,c}. Если слово P имеет чётную длину, то оставить в нём только левую половину.
23. A={0,1}. Считая непустое слово Р записью двоичного числа, получить это же число, но в четверичной системе. (Замечание: учесть, что в двоичном числе может быть нечётное количество цифр.)
|
|
|
24. A={0,1,2,3}. Считая непустое слово Р записью числа в четверичной системе счисления, получить запись этого числа в двоичной системе.
25. A={ | }. Считая слово Р записью числа в единичной системе счисления, получить запись этого числа в троичной системе. (Рекомендация: следует в цикле удалять из «единичного» числа по палочке и каждый раз прибавлять 1 к троичному числу, которое вначале положить равным 0.)
26. A={0,1,2}. Считая непустое слово Р записью числа в троичной системе счисления, получить запись этого числа в единичной системе.
27. A={a,b}. Если в P символов a больше, чем символов b, то выдать ответ a, если символов a меньше символов b, то выдать ответ b, а иначе в качестве ответа выдать пустое слово.
28. A={a,b,c}. Удвоить каждый символ в слове P (например: bacb → bbaaccbb).
29. A={0,1,2}. Считая непустое слово P записью положительного троичного числа, уменьшить это число на 1.
30. A={a,b}. Определить, является ли слово Р палиндромом (перевёртышем, симметричным словом). Ответ: слово а, если является, или пустое слово иначе.
31. A={ | }. Считая слово Р записью числа в единичной системе, определить, является ли это число степенью 3 (1, 3, 9, 27,…). Ответ: пустое слово, если является, или слово из одной палочки иначе.
|
|
|
32. A={ | }. Считая слово Р записью числа n в единичной системе, получить в этой же системе число 2n.
33.A={ | }. Пусть слово Р является записью числа 2n (n=0, 1, 2, в единичной системе. Получить в этой же системе число n.
34. Пусть P имеет вид Q=R, где Q и R - любые слова из символов a и b. Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе.
35. Пусть P имеет вид Q=R, где Q и R - непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.
36. Пусть P имеет вид Q>R, где Q и R - непустые слова из символов 0 и 1. Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями), выдать в качестве ответа слово 1, если число Q больше числа R, и слово 0 иначе.
Дата добавления: 2018-08-06; просмотров: 2263; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!