ИнформатикаЗадание 12
ЕГЭ 2027 по информатике
Задание 12. Машина Тьюринга и Редактор
- Первая часть
- краткий ответ: число или слово
- 1 первичный балл
- 19 задач в задачнике
Задачи проверяются сразу, ответ и разбор открываются после решения. Нужна бесплатная регистрация.
Как узнать: исполнитель МТ (машина Тьюринга) с лентой, головкой, состояниями q0, q1, … и таблицей команд. Или исполнитель Редактор, который заменяет подстроки в строке. В демоверсии 2027 года стоит МТ.
Частые ошибки
Примеры заданий
Пример 1. Машина Тьюринга, вариант 1
На ленте исполнителя МТ в соседних ячейках записано двоичное представление числа 5122 без ведущих нулей, остальные ячейки пустые (λ). В начальный момент головка находится в ближайшей справа от последовательности ячейке в состоянии q0. Программа:
| λ | 0 | 1 | |
|---|---|---|---|
| q0 | 0, L, q1 | ||
| q1 | 1, S, q1 | 0, L, q1 | 1, L, q1 |
Сколько единиц записано на ленте после остановки исполнителя?
Пример 2. Машина Тьюринга, вариант 2
На ленте исполнителя МТ в соседних ячейках записано двоичное представление числа 9256 без ведущих нулей, остальные ячейки пустые (λ). В начальный момент головка находится в ближайшей справа от последовательности ячейке в состоянии q0. Программа:
| λ | 0 | 1 | |
|---|---|---|---|
| q0 | λ, L, q1 | ||
| q1 | λ, S, q1 | 1, L, q1 | 0, L, q1 |
Определи результат: число, записанное на ленте после остановки, в десятичной системе (ведущие нули не важны).
Пример 3. Редактор, вариант 1
На вход Редактору подаётся строка, которая начинается с 0, а затем содержит 25 цифр 1 и 11 цифр 2 (сначала все единицы, потом все двойки). Команда «заменить» меняет первое слева вхождение. Какая строка получится после выполнения программы? В ответе запиши сумму цифр этой строки.
ПОКА нашлось (01) ИЛИ нашлось (02) ИЛИ нашлось (03)
заменить (01) на (30)
заменить (02) на (3103)
заменить (03) на (1201)
КОНЕЦ ПОКА