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»  на  «X»  и  останавливает  исполнителя  в первой ячейке слева от последовательности символов «X». 

Возможное начальное состояние исполнителя:

 

 

 

Конечное состояние исполнителя после завершения выполнения программы:

 

 

 

На ленте в соседних ячейках записана последовательность из \(1000\) символов, включающая   только   нули   и   единицы.   Ячейки   справа   и   слева  от  последовательности  заполнены пустыми  символами  «λ».  В  начальный момент  времени  головка  расположена  в  ближайшей  ячейке  справа  от последовательности. Программа работы исполнителя:  

 

	λ	\(1\)	\(0\)
\(q0\)	λ, L, \(q1\)
\(q1\)	λ, S, \(q1\)	\(0\), S, \(q1\)	\(1\), L, \(q1\)

 

После  выполнения  программы на ленте осталось ровно \(343\)  нуля. Определи максимально возможное число нулей в исходной последовательности.

 

Разберём работу программы исполнителя МТ с учётом заданных условий.

 

Исполнитель стартует в ячейке, расположенной непосредственно справа от анализируемой последовательности. Первым действием он выполняет команду перемещения влево — в сторону начала последовательности.

 

Логика работы алгоритма следующая:

 

При обнаружении символа «\(1\)» или «λ» выполнение программы немедленно завершается.

 

Если исполнитель встречает символ «\(0\)», он выполняет два действия:

 

заменяет «\(0\)» на «\(1\)»;

 

перемещается на одну ячейку влево.

 

Предположим, что исходная последовательность содержит \(1000\) символов и полностью состоит из нулей. В таком случае исполнитель последовательно заменит каждый «\(0\)» на «\(1\)», двигаясь от правого края к левому.

 

По условию после завершения работы программы в последовательности осталось \(343\) символа «\(0\)». Это позволяет сделать вывод о структуре исходной ленты:

 

слева располагались \(343\) нуля, которые исполнитель не успел обработать;

 

далее следовал хотя бы один символ «\(1\)» (или «λ»), ставший причиной остановки программы.

 

Чтобы определить максимально возможное количество нулей в исходной последовательности, нужно вычислить максимальное число «\(0\)» справа от стоп‑символа («\(1\)»/«λ»).

 

Расчёт:

 

общая длина последовательности: \(1000\) символов;

 

количество «\(0\)» слева от стоп‑символа: \(343\);

 

стоп‑символ («1»): \(1\) символ;

 

максимально возможное количество «\(0\)» справа от стоп‑символа: \(1000−343−1=656\).

 

Таким образом, наибольшее возможное число нулей в исходной последовательности складывается из двух частей:

 

\(343\) нуля слева от стоп‑символа (неизменённые);

 

\(656\) нулей справа от стоп‑символа (которые исполнитель успел заменить на «\(1\)»).

 

Итоговый результат: \(343+656=999\) символов «\(0\)».

 

Ответ: \(999\).