Условие задания:
1 Б.
Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов \(A = {a0, a1, ..., a(n~–1)})\), включая специальный пустой символ \(a0\). Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из множества допустимых состояний \(Q = {q0, q1, ..., q(n~–1)}\). В начальный момент времени головка находится в начальном состоянии \(q0\). На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остаётся в прежнем состоянии. Программа работы исполнителя МТ задаётся в табличном виде.
\(a0\) | \(a1\) | ... | \(a(n-1)\) | |
\(q0\) | команда | команда | ... | команда |
\(q1\) | команда | команда | ... | команда |
... | ... | ... | ... | ... |
\(q(n-1)\) | команда | команда | ... | команда |
В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце — возможные состояния головки. На пересечении \(i\)-й строки и \(j\)-го столбца находится команда, которую выполняет МТ, когда головка обозревает \(j\)-й символ, находясь в \(i\)-м состоянии. Если пара «символ — состояние» невозможна, то клетка для команды остаётся пустой. Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент — записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент — один из четырёх символов \(L\), \(R\), \(N\), \(S\). Символы \(L\) и \(R\) означают сдвиг в левую или правую ячейки соответственно, \(N\) — отсутствие сдвига, \(S\) — завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент — новое состояние головки после выполнения команды. Например, команда \(0\), \(L\), \(q3\) выполняется следующим образом: в текущую ячейку записывается символ \(0\), затем головка сдвигается в соседнюю слева ячейку и переходит в состояние \(q3\).
Приведём пример выполнения программы, заданной таблично.
На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов \(Z\), все остальные ячейки ленты заполнены пустым символом \(λ\). В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа \(Z\).
На ленте записано неизвестное ненулевое количество расположенных подряд в соседних ячейках символов \(Z\), все остальные ячейки ленты заполнены пустым символом \(λ\). В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа \(Z\).
Программа
\(λ\) | \(Z\) | |
\(q0\) | \(λ\), \(L\), \(q0\) | \(X\), \(L\), \(q1\) |
\(q1\) | \(λ\), \(S\), \(q1\) | \(X\), \(L\), \(q1\) |
заменяет на ленте все символы \(Z\) на \(X\) и останавливает исполнителя в первой ячейке слева от последовательности символов \(X\).
Возможное начальное состояние исполнителя:
... | \(λ\) | \(λ\) | \(Z\) | \(Z\) | \(Z\) | \(Z\) | \(λ\) | \(λ\) | … |
Конечное состояние исполнителя после завершения выполнения программы:
... | \(λ\) | \(λ\) | \(X\) | \(X\) | \(X\) | \(X\) | \(λ\) | \(λ\) | … |
Выполни задание.
На ленте в соседних ячейках записано двоичное представление числа 243615 без ведущих нулей. Ячейки справа и слева от последовательности заполнены пустыми символами \(λ\). В начальный момент времени головка расположена в ближайшей слева от последовательности ячейке.
Программа работы исполнителя:
\(λ\) | \(0\) | \(1\) | |
\(q0\) | \(1\), \(R\), \(q1\) | ||
\(q1\) | \(0\), \(R\), \(q2\) | \(0\), \(R\), \(q1\) | \(1\), \(S\), \(q1\) |
\(q2\) | \(0\), \(R\), \(q3\) | ||
\(q3\) | \(1\), \(S\), \(q3\) |
Определи результат работы программы. В ответе запиши получившееся на ленте число в десятичной системе счисления.
Ответ: .
Вы должны авторизоваться, чтобы ответить на задание. Пожалуйста, войдите в свой профиль на сайте или зарегистрируйтесь.
Вход
или
Регистрация