1. На ленте машины Тьюринга содержится последовательностью символов “+”. Напишите программу для машины Тьюринга, которая каждый второй символ “+” заменит на “–”. Замена начинается с правого конца последовательности. Автомат в состоянии q1 обозревает один из символов указанной последовательности. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
2. Дано число n в восьмеричной системе счисления. Разработать машину Тьюринга, которая увеличивала бы заданное число n на 1. Автомат в состоянии q1 обозревает некую цифру входного слова. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
3. Дана десятичная запись натурального числа n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
4. Дано натуральное число n > 1. Разработать машину Тьюринга, которая уменьшала бы заданное число n на 1, при этом в выходном слове старшая цифра не должна быть 0. Например, если входным словом было “100”, то выходным словом должно быть “99”, а не “099”. Автомат в состоянии q1 обозревает правую цифру числа. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
5. Дан массив из открывающих и закрывающих скобок. Построить машину Тьюринга, которая удаляла бы пары взаимных скобок, т.е. расположенных подряд “( )”.
Например, дано “) ( ( ) ( ( )”, надо получить “) . . . ( ( ”.
Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
6. Дана строка из букв “a” и “b”. Разработать машину Тьюринга, которая переместит все буквы “a” в левую, а буквы “b” — в правую части строки. Автомат в состоянии q1 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
var k1,k2,k3,k4,k:integer;
begin
writeln('Перед вами программа, которая умеет вычислять количество информации');
writeln('по выбранному наугад шарику из мешка.');
writeln('Введите число шаров белого цвета:');
readln(k1);
writeln('Введите число шаров чёрного цвета:');
readln(k2);
writeln('Введите число шаров синего цвета:');
readln(k3);
writeln('Введите число шаров красного цвета:');
readln(k4);
k:=k1+k2+k3+k4;
if k1<>0 then
writeln('Во фразе «Выпал белый шар» содержится ',log2(k/k1):4:1,' бит(а) информации');
if k2<>0 then
writeln('Во фразе «Выпал чёрный шар» содержится ',log2(k/k2):4:1,' бит(а) информации');
if k3<>0 then
writeln('Во фразе «Выпал синий шар» содержится ',log2(k/k3):4:1,' бит(а) информации');
if k4<>0 then
writeln('Во фразе «Выпал красный шар» содержится ',log2(k/k4):4:1,' бит(а) информации');
end.
Пример:
Перед вами программа, которая умеет вычислять количество информации
по выбранному наугад шарику из мешка.
Введите число шаров белого цвета:
100
Введите число шаров чёрного цвета:
0
Введите число шаров синего цвета:
200
Введите число шаров красного цвета:
100
Во фразе «Выпал белый шар» содержится 2.0 бит(а) информации
Во фразе «Выпал синий шар» содержится 1.0 бит(а) информации
Во фразе «Выпал красный шар» содержится 2.0 бит(а) информации
