Индивидуальное задание №4_1
Задание 1.
1) Построить нормальный алгоритм Маркова, который бы в слове из алфавита {a,b,c,d,e,f,λ} все вхождения последовательности abc заменял на символ f.
2) Построить нормальный алгоритм Маркова, который бы в слове из алфавита {a,b,c,d,e,f,λ} удалял все вхождения последовательности bc.
3) Построить нормальный алгоритм Маркова, который бы переворачивал любое заданное слово в алфавите А={0,1,2,3}.
4) Построить нормальный алгоритм Маркова, который бы в слове из алфавита {a,b,c,d,e,f,λ} все символы a заменял на f, а все f – на af.
5) Построить нормальный алгоритм Маркова, который бы в любом слове из алфавита А={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,r,s,t,u,v,w,x,y,z} удваивал все буквы, стоящие на четных местах в исходном слове.
6) Построить нормальный алгоритм Маркова, который в любом слове в алфавите А={a,b} переносит все буквы «а» в начало слова.
7) Поменять местами первый и последний символа слова в алфавите А={a,b,c,d,e}.
8) Даны два слова из букв, записанные через пробел в алфавите А={a,b,c,d,e,f,,>,<,=}. Вместо пробела поставить >, <, =.
9) Построить нормальный алгоритм Маркова, реализующий циклический сдвиг первого символа слова в алфавите А={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,r,s,t,u,v,w,x,y,z}.
10) Построить нормальный алгоритм Маркова, который бы в слове из алфавита {a,b,c,d,e,f,λ} все вхождения последовательности cde заменял на символ a.
11) Построить нормальный алгоритм Маркова, который бы в слове из алфавита {a,b,c,d,e,f,λ} удалял все вхождения последовательности fe.
12) Построить нормальный алгоритм Маркова, который бы переворачивал любое заданное слово в алфавите А={a,b,c,d}.
13) Построить нормальный алгоритм Маркова, который бы в слове из алфавита {a,b,c,d,e,f,λ} все символы e заменял на d, а все d – на de.
14) Построить нормальный алгоритм Маркова, который бы в любом слове из алфавита А={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,r,s,t,u,v,w,x,y,z} удваивал все гласные буквы.
15) Построить нормальный алгоритм Маркова, который в любом слове в алфавите А={a,b} переносит все буквы «а» в конец слова.
16) Поменять местами первый и последний символа слова в алфавите А={0,1,2,3,4,5}.
17) Построить нормальный алгоритм Маркова, реализующий циклический сдвиг последнего символа слова в алфавите А={a,b,c,d,e,f,g,h,i,j,k,l,m,n,o,p,r,s,t,u,v,w,x,y,z}.
18) Построить нормальный алгоритм Маркова для вычисления функции f(x)=x mod 3 в унарной системе счисления.
19) Построить нормальный алгоритм Маркова для вычисления функции f(x)=x div 3 в унарной системе счисления.
20) Построить нормальный алгоритм Маркова для перевода числа из двоичной системы счисления в восьмеричную.
21) Построить нормальный алгоритм Маркова для перевода числа из двоичной системы счисления в четверичную.
Задание 2 (на 0.2 балла).
1. Построить нормальный алгоритм Маркова для определения системы счисления (найти возможное минимальное основание), в которой записано натуральное число (предполагается, что основание не может превышать 1610).
2. Даны два слова в унарной системе, записанные через *. Вместо звездочки поставить >, <, =.
3. A ={0,1}. Считая непустое слово P записью двоичного числа, определить,
является ли это число степенью 2 (1, 2, 4, …). Ответ: слово 1, если является, или
слово 0 иначе.
4. A ={0,1,2,3}. Считая непустое слово P записью четверичного числа, про-
верить, чётно оно или нет. Ответ: слово 0, если чётно, и слово 1 иначе.
5. A ={0,1,2,3}. Считая непустое слово P записью четверичного числа,
получить остаток от деления этого числа на 4.
6. A ={0,1}. Считая непустое слово P записью двоичного числа, получить это
же число, но в четверичной системе. (Замечание: учесть, что в двоичном числе
может быть нечётное количество цифр.)
7. A ={0,1,2}. Считая непустое слово P записью троичного числа, увеличить это число на 1.
8. A ={0,1,2}. Считая непустое слово P записью положительного троичного
числа, уменьшить это число на 1.
9. A ={ | }. Считая слово P записью числа в единичной системе счисления,
получить запись этого числа в троичной системе. (Рекомендация: следует в
цикле удалять из «единичного» числа по палочке и каждый раз прибавлять 1 к
троичному числу, которое вначале положить равным 0.)
10. A ={0,1,2}. Считая непустое слово P записью числа в троичной системе,
получить запись этого числа в единичной системе.
11. A ={ a, b, c }. Определить, входит ли первый символ непустого слова P ещё
раз в это слово. Ответ: слово a, если входит, или пустое слово иначе.
12. A ={ a, b }. Перенести первый символ непустого слова P в конец слова.
13. A ={ a, b }. Перенести последний символ непустого слова P в начало слова.
14. A ={ a, b }. В непустом слове P переставить первый и последний символы.
15. A ={ a, b }. Если в непустом слове P совпадают первый и последний
символы, то удалить оба этих символа, а иначе слово не менять.
16. A ={ a, b }. Определить, является ли слово P палиндромом (перевёртышем,
симметричным словом). Ответ: слово a, если является, или пустое слово иначе.
17. A ={ a, b }. Пусть слово P имеет нечётную длину. Удалить из него средний
символ
24. Пусть P имеет вид Q = R, где Q и R – любые слова из символов a и b.
Выдать ответ a, если слова Q и R одинаковы, и пустое слово иначе.
25. Пусть P имеет вид Q = R, где Q и R – непустые слова из символов 0 и 1.
Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями),
выдать в качестве ответа слово 1, если эти числа равны, и слово 0 иначе.
26. Пусть P имеет вид Q > R, где Q и R – непустые слова из символов 0 и 1.
Трактуя Q и R как записи двоичных чисел (возможно, с незначащими нулями),
выдать в качестве ответа слово 1, если число Q больше числа R, и слово 1 иначе.
27. A ={(,)}. Определить, сбалансировано ли слово P по круглым скобкам.
Ответ: Д (да) или Н (нет)
28. A ={ a, b }. Перевернуть слово P (например: abb → bba).