Решение задачи МТ: Преобразование двоичного числа 135

Решение задачи №1: 1. Переведем число 135 в двоичную систему счисления: \[ 135_{10} = 128 + 4 + 2 + 1 = 2^7 + 2^2 + 2^1 + 2^0 = 10000111_2 \] На ленте записано: \( 10000111 \). Головка находится справа от числа на пустом символе \( \lambda \), состояние \( q_0 \). 2. Выполним алгоритм по шагам: - Состояние \( q_0 \), символ \( \lambda \): по таблице выполняем \( \lambda, L, q_1 \). (Оставляем \( \lambda \), сдвиг влево, переход в \( q_1 \)). Теперь головка стоит на последней единице числа. - Состояние \( q_1 \), символ 1: по таблице выполняем \( 0, L, q_1 \). (Заменяем 1 на 0, сдвиг влево). - Состояние \( q_1 \), символ 1: снова заменяем 1 на 0, сдвиг влево. - Состояние \( q_1 \), символ 1: снова заменяем 1 на 0, сдвиг влево. - Состояние \( q_1 \), символ 0: по таблице выполняем \( 1, L, q_1 \). (Заменяем 0 на 1, сдвиг влево). - Далее для всех оставшихся нулей (их три) в состоянии \( q_1 \) они будут заменены на 1, а самая первая единица будет заменена на 0. - Когда головка дойдет до пустого символа \( \lambda \) слева от числа, сработает команда \( \lambda, S, q_1 \), и программа зациклится или остановится (в зависимости от трактовки S как Stop). Однако, анализируя таблицу, мы видим инверсию всех разрядов числа: 1 меняется на 0, а 0 на 1. Было: \( 10000111 \) Стало: \( 01111000 \) 3. Переведем результат в десятичную систему: \[ 01111000_2 = 64 + 32 + 16 + 8 = 120 \] Ответ: 120 Решение задачи №2: 1. Переведем число 2028 в двоичную систему счисления: \[ 2028 = 1024 + 512 + 256 + 128 + 64 + 32 + 8 + 4 \] \[ 2028_{10} = 11111101100_2 \] Головка находится слева от числа на символе \( \lambda \), состояние \( q_0 \). 2. Выполним алгоритм: - \( q_0, \lambda \rightarrow \lambda, R, q_1 \): сдвиг вправо на первую цифру числа. - В состоянии \( q_1 \) головка идет вправо, пока не встретит 0. Команда для 1: \( 1, R, q_1 \). Команда для 0: \( 0, R, q_2 \). - В нашем числе \( 11111101100 \) первый ноль стоит на 7-й позиции. Дойдя до него, переходим в \( q_2 \). - В состоянии \( q_2 \) любая цифра (в таблице пусто, но по логике \( q_1 \) и \( q_3 \)) или следующий символ заменяется на 0, и переход в \( q_3 \). - В состоянии \( q_3 \) при встрече \( \lambda \) программа останавливается (\( S \)). Судя по логике команд \( q_1 \rightarrow q_2 \rightarrow q_3 \), программа находит первый ноль и заменяет следующий за ним символ на 0. Исходное: \( 11111101100 \) После \( q_1 \) (встретили 0 на 7-й позиции): головка на 8-й позиции (там 1). После \( q_2 \): заменяем эту 1 на 0. Результат: \( 11111100100 \) 3. Переведем в десятичную систему: \[ 11111100100_2 = 1024 + 512 + 256 + 128 + 64 + 32 + 4 = 2020 \] Ответ: 2020