§ 8. Формальный исполнитель: автомат

Определения и обозначения

Формальный исполнитель — объект, который выполняет команды строго по заданным правилам и не проявляет самостоятельности. Он не придумывает решение и не меняет алгоритм по своему желанию. Такое понятие нужно, чтобы точно описывать работу устройства или программы.

Автомат — формальный исполнитель, способный менять своё состояние под воздействием входных сигналов или команд. Например, устройство может перейти из режима ожидания в режим работы после нажатия кнопки. Автомат удобен для описания процессов, где дальнейшие действия зависят от уже полученных сигналов.

Состояние автомата — описание его положения в данный момент, от которого зависит дальнейшее поведение. Состояния можно обозначать q₀, q₁, q₂ или любыми другими именами. Они позволяют хранить существенную для работы информацию, не расписывая всю историю событий.

Алфавит — конечное множество входных сигналов или символов, которые может воспринимать автомат. Например, алфавит может состоять из символов 0 и 1: {0, 1}. Он ограничивает набор допустимых команд, поступающих на вход.

Как это устроено

У автомата должно быть конечное множество состояний, потому что его работу нужно полностью перечислить и однозначно описать. Для каждого состояния задаются правила реакции на входные сигналы, поэтому бесконечное число вариантов нельзя было бы практически представить в таблице или схеме. Конечность делает поведение автомата проверяемым и позволяет реализовать его в программе или устройстве.

Входной сигнал вызывает переход из текущего состояния в новое согласно заданному правилу. Вместе с переходом может выполняться действие: например, автомат может выдать символ, включить лампу или изменить счётчик. Сначала определяется состояние до сигнала, затем выбирается правило и только после этого фиксируется новое состояние.

Описание автомата включает несколько частей: множество состояний, входной алфавит, начальное состояние и правила переходов. Начальное состояние необходимо, потому что до обработки первого символа автомат уже должен находиться в каком-то положении. Если хотя бы один из этих элементов не задан, последовательность работы может оказаться неоднозначной.

Один и тот же сигнал способен приводить к разным действиям в зависимости от текущего состояния. Например, сигнал 1 в состоянии «ожидание» может запустить процесс, а в состоянии «работа» — остановить его. Поэтому при анализе нельзя смотреть только на очередной символ: нужно одновременно учитывать состояние, в котором автомат его получил.

Работу автомата удобно представить таблицей переходов или схемой. В таблице строки соответствуют состояниям, столбцы — входным сигналам, а клетки содержат новое состояние и, если нужно, действие. На схеме состояния изображают вершинами, а переходы — стрелками с подписями сигналов; начальное состояние отмечают отдельно.

Основные элементы и характеристики конечного автомата

Чтобы воспользоваться таблицей, сначала найдите строку начального состояния. Затем читайте входную последовательность слева направо и каждый раз выбирайте столбец очередного сигнала.

Число в найденной клетке становится текущим состоянием для следующего шага. Если в клетке указано действие или результат, его также записывают.

Разбор задач

Задача 1. Обработка последовательности

Автомат имеет состояния q₀ и q₁. Из q₀ по сигналу 0 он переходит в q₁, а по сигналу 1 остаётся в q₀. Из q₁ правила не указаны, поэтому для продолжения нужно считать, что автомат возвращается в q₀ по 1 и остаётся в q₁ по 0. Определим состояние после обработки 1010, начиная с q₀.

1. Получаем 1 в состоянии q₀: остаёмся в q₀.
2. Получаем 0 в состоянии q₀: переходим в q₁.
3. Получаем 1 в состоянии q₁: возвращаемся в q₀.
4. Получаем 0 в состоянии q₀: переходим в q₁.

Ответ: после обработки последовательности 1010 автомат находится в состоянии q₁. Решение показывает, почему символы нельзя обрабатывать независимо: каждый следующий переход начинается из состояния, полученного на предыдущем шаге.

Задача 2. Построение схемы

По таблице переходов нужно построить схему автомата с тремя состояниями и указать путь при обработке слова 01101. Обозначим состояния q₀, q₁ и q₂, а начальным будем считать q₀; стрелку подписываем тем символом, который вызывает переход.

1. Для каждой клетки таблицы проведите стрелку из состояния строки в состояние, указанное в клетке.
2. Если несколько сигналов ведут в одну и ту же вершину, подпишите их на одной стрелке или нарисуйте отдельные стрелки.
3. Начните путь в q₀ и последовательно подпишите переходы по символам 0, 1, 1, 0, 1, каждый раз переходя в новую вершину.

Ответ: схема строится непосредственным переносом всех правил из таблицы, а искомый путь записывается как цепочка из шести состояний: начального и пяти полученных после сигналов. Конкретные вершины цепочки определяются значениями таблицы.

Задача 3. Автомат для проверки последнего символа

Нужно принимать последовательность, если она заканчивается символом 1, и отвергать её в остальных случаях. Достаточно хранить не всю последовательность, а только информацию о последнем обработанном символе.

1. Создадим состояние q₀: последовательность пуста или её последний символ равен 0; это состояние отвергания.
2. Создадим состояние q₁: последний обработанный символ равен 1; это состояние принятия.
3. Из любого состояния по 0 переходим в q₀, а по 1 — в q₁. Начальным назначаем q₀.

Ответ: автомат принимает слово тогда, когда после обработки всех символов находится в q₁. Например, 01101 принимается, а 1100 отвергается, потому что последнее состояние определяется последним символом.

Типичные ошибки

Автомат считают разумным исполнителем. Ошибка возникает из-за привычки приписывать устройствам самостоятельный выбор. Проверьте себя: для каждого шага должно находиться заранее заданное правило, а не объяснение «автомат решил сам».

Состояние путают с входным сигналом. Сигнал поступает извне и вызывает переход, а состояние сохраняется после шага и влияет на следующую реакцию. Чтобы проверить различие, выпишите отдельно входное слово и цепочку состояний.

Забывают начальное состояние. Без него первый переход неизвестен, поэтому итог обработки нельзя определить однозначно. Перед решением всегда отмечайте, из какого состояния начинается работа.

Не задают переход для допустимого сигнала. Тогда автомат может остановиться или его поведение окажется неописанным. Проверьте каждую строку таблицы: для каждого символа входного алфавита должно быть указано правило либо специальное условие.

Связь с другими темами

Для изучения автоматов нужны понятия алгоритма, исполнителя, команды, последовательности команд и условного выбора. Дальше эта тема помогает понимать алгоритмы, логические схемы, языки программирования и моделирование процессов. Автоматическая обработка строк и распознавание последовательностей основаны на переходах между состояниями.

Что запомнить

• Автомат является формальным исполнителем.
• Работа автомата определяется его состоянием и входными сигналами.
• После каждого сигнала автомат переходит в новое состояние по заданному правилу.
• Описание автомата включает состояния, входной алфавит, начальное состояние и переходы.
• Один и тот же сигнал может вызывать разные переходы в разных состояниях.
• Работу автомата можно представить таблицей переходов или схемой.
• Чтобы определить результат работы, нужно обработать входную последовательность по шагам.