Задание 12: Выполнение алгоритмов для исполнителей

Задание находится в части 1, оценивается в 1 балл, ответ — целое число, калькулятор не нужен, но нужна аккуратность. Условие почти всегда содержит: полное описание правил исполнителя (алфавит, состояния, формат команды), иллюстративный пример работы программы на маленькой ленте или строке, и собственно вопрос: дана лента/строка большой длины (сотни-тысячи символов), известен результат после выполнения программы, требуется найти характеристику исходных данных — максимальное или минимальное количество символов определённого вида. Программа исполнителя из года в год похожа почти буквально, меняют …

Машина Тьюринга:

• Алфавит $A=\{a_0,a_1,\dots,a_{n-1}\}$, где $a_0=\lambda$ — пустой символ.
• Множество состояний $Q=\{q_0,q_1,\dots,q_{m-1}\}$, начальное состояние всегда $q_0$.
• Команда в ячейке таблицы — тройка (записываемый символ; сдвиг $L/R/N$; новое состояние); команда с завершением помечается $S$.
• Порядок символов в заголовке таблицы совпадает с порядком, в котором алфавит перечислен в условии (например $\lambda,1,0$, а не привычные $\lambda,0,1$) — это нужно проверять каждый раз.
• Сдвиг головки происходит после записи символа в текущую ячейку.
• Работа завершается только по команде с символом $S$.

Исполнитель Редактор:

• Хранит одну строку символов; программа состоит из команд «заменить (a, b)» — заменить первое найденное вхождение подстроки $a$ на $b$, и логической проверки «нашлось(a)».
• Типичная конструкция: ПОКА нашлось(a) ЗАМЕНИТЬ (a, b) — выполняется, пока подстрока $a$ встречается в строке.
• Замена всегда происходит по самому левому вхождению, после чего поиск начинается заново с начала строки.

Общее: задачи почти всегда просят связать длину/состав исходных данных с длиной/составом результата через одну переменную-параметр (например, длину серии одинаковых символов у края последовательности); итоговый ответ — целое число, значит все промежуточные величины должны быть целыми.

1. Прочитать описание исполнителя и зафиксировать реальный порядок столбцов/строк таблицы — порядок алфавита часто отличается от привычного и меняет смысл программы.
2. Определить начальное состояние головки, её начальное положение и направление движения.
3. Вручную выполнить 3–5 тактов на коротком примере, чтобы понять, что именно делает программа: движение до границы, замена символов, подсчёт и т.п.
4. Сформулировать правило работы программы словами.
5. Ввести параметр (обычно длину серии одинаковых символов у края) и выразить конечный результат через исходные данные и этот параметр.
6. Определить допустимый диапазон параметра с учётом длины всей последовательности и целочисленности.
7. Подставить границы диапазона и выбрать значение параметра, дающее нужный максимум или минимум искомой величины. …