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 обозревает крайний левый символ строки. Кроме самой программы-таблицы, описать словами, что выполняется машиной в каждом состоянии.
1) 100101₂
2) 45₁₀
3) 175₈
4) 335₁₀
Объяснение:
Для перевода числа из 10 системы счисления в любую другую систему счисления надо нацело делить число на основание новой системы счисления (пока целая часть не станет равной 0) и записывать получившиеся остатки от деления. Число в новой системе счисления записывается в виде остатков деления, начиная с последнего
1) 37₁₀ → А₂
37/2 = 18 и остаток 1
18/2 = 9 и остаток 0
9/2 = 4 и остаток 1
4/2 = 2 и остаток 0
2/2 = 1 и остаток 0
1/2 = 0 и остаток 1
37₁₀ = 100101₂
3) 125₁₀ → А₈
125/8 = 15 и остаток 5
15/8 = 1 и остаток 7
1/8 = 0 и остаток 1
125₁₀ = 175₈
Для перевода числа из любой системы счисления в 10 систему счисления используется развернутая запись числа - сумма произведений цифр числа на основание системы счисления числа в степени разряда цифры числа
2) 101101₂ → А₁₀
101101₂ = 1 * 2⁵ + 0 * 2⁴ + 1 * 2³ + 1 * 2² + 0 * 2¹ + 1 * 2⁰ = 32 + 0 + 8 + 4 + 0 + 1 = 45₁₀
4) 517₈ → А₁₀
517₈ = = 5 * 8² + 1 * 8¹ + 7 * 8⁰ = 320 + 8 + 7 = 335₁₀