Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделённой на равные ячейки. В каждой ячейке ленты находится ровно один символ из алфавита исполнителя, включая специальный пустой символ «λ», обозначающий пустую ячейку.
Программа работы исполнителя задаётся таблицей. В первой строке таблицы перечислены все возможные символы, которые могут находиться в текущей ячейке ленты, в первом столбце — все возможные состояния головки. На пересечении i-й строки и j-го столбца таблицы находится команда, которую должна выполнить машина Тьюринга, если головка находится в состоянии, соответствующем i-й строке, и обозревает символ, соответствующий j-му столбцу. Если для некоторой пары «символ — состояние» команда в таблице отсутствует, это означает, что такая пара при работе исполнителя не встречается.
Каждая команда состоит из трёх элементов, записанных через запятую. Первый элемент — символ алфавита, который следует записать в текущую ячейку (он может совпадать с тем, который уже там записан). Второй элемент — один из символов «L», «R», «N», «S»: символы «L» и «R» означают сдвиг головки на одну ячейку влево или вправо соответственно, символ «N» означает отсутствие сдвига, а символ «S» означает, что после выполнения текущей команды работа исполнителя завершается. Сдвиг головки происходит после записи символа в текущую ячейку. Третий элемент — новое состояние, в которое переходит головка после выполнения команды.
Например, команда 0, L, q3 означает следующее: в текущую ячейку записывается символ «0», затем головка сдвигается на одну ячейку влево и переходит в состояние q3.
Задание. Напишите функцию run(tape, head, rules), которая моделирует работу исполнителя МТ.
Параметры:
tape — строка из символов ленты; ячейка с индексом 0 — самая левая;head — стартовая позиция головки. Может быть равна -1 (головка левее ленты) или len(tape) (правее ленты);rules — словарь программы: ключ — кортеж (состояние, символ), значение — кортеж (записываемый_символ, сдвиг, новое_состояние). Сдвиг — одна из строк 'L', 'R', 'N', 'S'.
Пустой символ «λ» обозначается символом подчёркивания '_'. Начальное состояние — 'q0'.
Функция должна вернуть кортеж из двух элементов: строку ленты от самой левой до самой правой непустой ячейки и количество выполненных шагов. Шагом считается каждое выполнение команды, включая команду с 'S'.
Если для пары «состояние — символ» команды в словаре нет, работа прекращается.
Пример: для ленты '1011000', head = 7 и программы вычитания единицы функция должна вернуть ('1010111', 5).