Учебно-методический комплекс дисциплины для обучающегося «Языки программирования» для специальности 5В010900 Математика
Тема 2. Композиции машин Тьюринга и нормальных алгоритмов Маркова
жүктеу/скачать 1.33 Mb.
|
| Тема 2. Композиции машин Тьюринга и нормальных алгоритмов Маркова.
Задачи для самостоятельного решения Замечания: В задачах рассматриваются только целые неотрицательные числа, если не сказано иное. Под «единичной» системой счисления понимается запись неотрицательного целого числа с помощью палочек - должно быть выписано столько палочек, какова величина числа; например: 2→ ||,5→ |||||,0 → <пустое слово>. A={f,h,p}. В слове P заменить все пары ph наf A={f,h,p}. В слове P заменить на f только первую пару ph, если такая есть. A={a,b,c}. Приписать слово bac слева к слову P. A={a,b,c}. Заменить слово P на пустое слово, т.е. удалить из P все символы. A={a,b,c}. Заменить любое входное слово на слово a. Выписать НАМ, не меняющий входное слово (при любом алфавите A) A={ | }. Считая слово P записью числа в единичной системе счисления, получить остаток от деления этого числа на 2, т.е. получить слово из одной палочки, если число нечетно, или пустое слово, если число четно. A={ | }. Считая слово P записью положительного числа в единичной системе счисления, уменьшить это число на 1. A={ | }. Считая слово P записью числа в единичной системе счисления, увеличить это число на 2. A={0,1,2}. Считая слово P записью числа в троичной системе счисления, получить остаток от деления этого числа на 2, т.е. получить слово 1, если число нечетно, или слово 0, если число четно. (Замечание: в четном троичном числе должно быть четное количество цифр 1.) A={a,b,c}. Определить, входит ли символ a в слово P. Ответ (выходное слово): слово a, если входит, или пустое слово, если не входит. A={a,b}. Если в слово P входит больше символов a, чем символов b, то в качестве ответа выдать слово из одного символа a, если в P равное количество a и b, то в качестве ответа выдать пустое слово, а иначе выдать ответ b. A={0,1,2,3}. Преобразовать слово P так, чтобы сначала шли все четные цифры (0 и 2), а затем - все нечетные. A={a,b,c}. Преобразовать слово P так, чтобы сначала шли все символы a, затем - все символы b и в конце - все символы c. A={a,b,c}. Определить, из скольких различных символов составлено слово P; ответ получить в единичной системе счисления (например: acaac→ | |). A={a,b,c}. В непустом слове P удвоить первый символ, т.е. приписать этот символ слева к P. A={a,b,c}. За первым символом непустого слова P вставить символ c. A={a,b,c}. Из слова P удалить второй символ, если такой есть. A={a,b,c}. Если в слове P не менее двух символов, то переставить два первых символа. A={0,1,2}. Считая непустое слово P записью троичного числа, удалить из этой записи все незначащие нули. жүктеу/скачать 1.33 Mb. Достарыңызбен бөлісу:
|