Исполнитель МТ работает с бесконечной лентой, разделённой на ячейки; в каждой ячейке — символ «0», «1» или пустой символ «λ». В начальный момент исполнитель находится в состоянии q0, головка над указанной ячейкой. Команда имеет вид «записать, движение, состояние»: движение L — влево, R — вправо, N — без сдвига, S — остановка работы после записи символа. Если для пары «символ — состояние» нет команды, работа завершается. Тактом называется выполнение одной команды.
Программа (таблица команд):
состояние λ 0 1
--------- -------- -------- --------
q0 λ, L, q1 — —
q1 λ, S, q1 1, L, q2 1, L, q2
q2 λ, S, q1 0, L, q1 1, L, q1
Лента (ячейки приведены слева направо, дальше все ячейки пусты): 000000000000000000. Головка находится в первой пустой ячейке справа от последовательности (все 18 ячеек последовательности правее неё; в состоянии q0 есть команда только для пустой ячейки).
Известно, что последовательность занимает ровно 18 ячеек, все остальные ячейки ленты пусты, и после выполнения программы на ленте осталось ровно 4 нулей. Определите наибольшее возможное число нулей в исходной последовательности.
В ответе…
Программа (таблица команд):
состояние λ 0 1
--------- -------- -------- --------
q0 λ, L, q1 — —
q1 λ, S, q1 1, L, q2 1, L, q2
q2 λ, S, q1 0, L, q1 1, L, q1
Лента (ячейки приведены слева направо, дальше все ячейки пусты): 000000000000000000. Головка находится в первой пустой ячейке справа от последовательности (все 18 ячеек последовательности правее неё; в состоянии q0 есть команда только для пустой ячейки).
Известно, что последовательность занимает ровно 18 ячеек, все остальные ячейки ленты пусты, и после выполнения программы на ленте осталось ровно 4 нулей. Определите наибольшее возможное число нулей в исходной последовательности.
В ответе…
Подсказка 1. Проследите, в каких состояниях головка меняет символы, а в каких оставляет их без изменений.
Подсказка 2. Головка обходит последовательность справа налево, меняясь между q1 и q2: в одном состоянии символ становится единицей, в другом остаётся прежним.
Подсказка 3. Все нечётные позиции справа (их 9) превращаются в единицы, поэтому нули остаются только на чётных позициях справа: 4 + 9.
Разбор.
Приём — трассировка алгоритма по тактам. Головка входит в последовательность справа в состоянии q1; в q1 любой символ заменяется на единицу, в q2 символ остаётся прежним, поэтому единицы записываются через одну клетку. Все нули на нечётных позициях справа (их 9) превращаются в единицы, а нули могут остаться только на чётных позициях справа (таких позиций 9). По условию нулей остаётся ровно 4, значит ровно столько чётных позиций заняты нулями, а все нечётные позиции изначально могут быть нулями — тогда общее число нулей максимально: 4 + 9 = 13. Проверка на примере 000000001010101010: после выполнения программы остаётся 4 нулей.
Ответ: 13.
Ответ.
13