Задание 12 из ЕГЭ по информатике: задача 4

Исполнитель МТ представляет собой читающую и записывающую головку, которая может перемещаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (A = {a0, a1, …, an–1}), включая специальный пустой символ λ.

Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний (Q = {q0, q1, …, qn–1}. В начальный момент времени головка находится в начальном состоянии q0.

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка может:

• Переместиться в соседнюю ячейку слева или справа, не меняя символ в текущей ячейке;
• Или заменить символ в текущей ячейке без перемещения;
• После выполнения действия перейти в новое состояние или остаться в прежнем.

Программа работы исполнителя задаётся в табличном виде. В первой строке перечислены все возможные символы ленты, в первой колонке – возможные состояния головки. На пересечении строки и столбца указана команда, которую выполняет МТ, когда головка обозревает данный символ, находясь в данном состоянии. Пустая клетка означает невозможную комбинацию.

Каждая команда имеет три элемента, разделённых запятой:

1. Символ, записываемый в текущую ячейку;
2. Действие: L (сдвиг влево), R (сдвиг вправо), N (без сдвига), S (завершение работы);
3. Новое состояние головки после выполнения команды.

Например, команда 0, L, q3 означает: в текущую ячейку записать символ «0», сдвинуться в соседнюю ячейку слева и перейти в состояние q3.

Выполните задание:

На ленте в соседних ячейках записано двоичное представление числа 511 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами «λ». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности в состоянии q0.

Программа работы исполнителя:

Определите десятичное представления числа на ленте исполнителя после его работы.