4 Метод — пошаговая трассировка
Метод — пошаговая трассировка
Надёжнее всего вести таблицу шагов: на каждом шаге фиксируем состояние, символ под кареткой и что получилось. Так ничего не потеряешь.
1. Прочитай условие и выпиши программу-таблицу.
2. Разберись, что делает машина, на маленьком примере (2–3 символа).
3. Веди пошаговую запись: состояние → символ → действие → новая лента.
4. Дойди до команды стоп и запиши результат.
5. Если спрашивают про исходные данные — рассуждай от результата назад.
Пример: разбор по шагам
Условие На ленте записано число 1023 в двоичной системе (это десять единиц подряд: |
Прослеживаем работу:
Шаг | Что делает машина | Лента |
|---|---|---|
старт | 1023 = десять единиц, каретка справа на λ |
|
сдвиг влево | команда |
|
проход по единицам | в q₁ каждую |
|
слева пусто | дошли до λ слева — пишем |
|
стоп | команда |
|
Итоговая запись 10000000000₂ в десятичной системе — это 1024.
Ответ: 1024 |
Проверка по смыслу: 1023 = 2¹⁰ − 1 (десять единиц), а после обработки получилось 2¹⁰ = 1024.