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

На ленте могут меняться только единицы, если исполнитель при этом находится в состоянии \(q_3.\) Поэтому нужно так составить начальную ленту, чтобы исполнитель в это состояние не перешёл. Заметим теперь, что в \(q_3\) исполнитель перейдёт, если встретятся две подряд идущие единицы. Значит, если мы хотим разместить на ленте как можно больше единиц, то мы должны чередовать их с нулями. А так как непустых символов у нас нечётное число, то начать заполнять ленту мы должны с единицы. Итак, строка из \(2025\) непустых символов, которая не меняется в результате исполнения алгоритма следующая: $$\lambda \underbrace{1010101 \ldots 10101}_{2025} \lambda$$ Всего в такой ленте \(1013\) единиц.

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

Python

tab = {('q0', 'l'): 'l,R,q0', ('q0', '0'): '0,N,q1', ('q0', '1'): '1,N,q1',
       ('q1', 'l'): 'l,S,q0', ('q1', '0'): '0,R,q1', ('q1', '1'): '1,R,q2',
       ('q2', 'l'): 'l,S,q0', ('q2', '0'): '0,R,q1', ('q2', '1'): '1,R,q3',
       ('q3', 'l'): 'l,S,q0', ('q3', '0'): '0,R,q3', ('q3', '1'): '0,R,q1',}
move = {'R': 1, 'S': 0, 'N': 0}

s = '10' * 1012

strip0 = ['l'] + list(s) + ['1'] + ['l']
strip = ['l'] + list(s) + ['1'] + ['l']
print('Количество 1 в исходной строке', strip0.count('1'))
p = 0
act = 'R'
state = 'q0'

while act != 'S':
    strip[p], act, state = tab[(state, strip[p])].split(',')
    p += move[act]
print(strip0 == strip)

Ответ: \(1013\)