Задание 12. Информатика. ЕГЭ. Поляков-8268

Пусть пустой символ \(\lambda\) стоит на нулевой позиции, а далее на \(1000\) следующих позициях стоят нули и единицы. Исполнитель завершает работу если он находится в состоянии \(q_1\) или \(q_2\) и смотрит на пустой символ, либо в состоянии \(q_2\) и на ленте в данный момент находится символ \(0.\) Если строка состоит из всех единиц, то в конце получится \(500\) нулей: каждая единица, находящаяся на нечётной позиции превратится в ноль. Рассмотрим следующую строку: $$\lambda \underbrace{11\ldots 1}_{397} 0 \underbrace{11\ldots 1}_{602}$$ Из первых \(397\) единиц получится \(199\) нулей (столько единиц стоит на нечётных позициях). На \(398\)-м шаге исполнитель остановится, так как встретит символ \(0\) и будет находиться в состоянии \(q_2.\) Всего получим \(200\) нулей. Таким образом, максимальное количество единиц в такой последовательности — \(999.\)

Проверяем программно

Python

mt = {'l': {'q0': 'l,R,q1', 'q1': 'l,S,q1', 'q2': 'l,S,q2'},
      '0': {'q1': '1,R,q2', 'q2': '0,S,q2'},
      '1': {'q1': '0,R,q2', 'q2': '1,R,q1'}}
#s = ['l'] + ['1'] * 1000 + ['l'] Если в строке 1000 единиц, то в конце получим 500 нулей
s = ['l']  + ['1'] * 397 + ['0'] + ['1'] * 602 + ['l']
p = 0
step = {'L': -1, 'R': 1, 'S': 0}
print(f'Количество единиц в начальной строке: {s.count("1")}')
state = 'q0'
act = mt[s[p]][state].split(',')
s[p] = act[0]
state = act[2]
while act[1] != 'S':
    p += step[act[1]]
    act = mt[s[p]][state].split(',')
    s[p] = act[0]
    state = act[2]
print(f'Количество нулей в конечной строке: {s.count("0")}')

Ответ: \(999\)