Автомат Мура

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

История

Концепция конечного автомата, в котором выход определяется только состоянием, была впервые формально описана американским математиком Эдвардом Форрестом Муром (Edward F. Moore) в 1956 году в статье «Gedanken-experiments on Sequential Machines». В этой работе Мур предложил модель, которая стала одной из фундаментальных в теории автоматов. Впоследствии модель получила название «автомат Мура» в честь её автора. Развитие цифровой электроники в 1960-х годах привело к широкому внедрению этой модели при проектировании синхронных цифровых схем, так как она обеспечивает более простую и предсказуемую синхронизацию выходных сигналов по сравнению с автоматом Мили.

Определение и формальная модель

Формально автомат Мура представляет собой шестёрку объектов:

\[ M = (S, X, Y, \delta, \lambda, s_0) \]

где:

• \( S \) — конечное множество состояний.
• \( X \) — конечное множество входных символов (входной алфавит).
• \( Y \) — конечное множество выходных символов (выходной алфавит).
• \( \delta: S \times X \rightarrow S \) — функция переходов, определяющая следующее состояние на основе текущего состояния и входного сигнала.
• \( \lambda: S \rightarrow Y \) — функция выходов, ставящая в соответствие каждому состоянию определённый выходной сигнал.
• \( s_0 \in S \) — начальное состояние.

Ключевое отличие от автомата Мили заключается в том, что функция выходов \( \lambda \) не зависит от входного сигнала. В автомате Мили выход определяется как \( \lambda(s, x) \), то есть зависит и от состояния, и от входа.

Принцип работы

Работа автомата Мура происходит в дискретные моменты времени, так называемые такты. В каждом такте:

1. Автомат находится в некотором текущем состоянии \( s \).
2. На вход подаётся символ \( x \in X \).
3. Выходной сигнал \( y = \lambda(s) \) формируется на основе текущего состояния (до прихода нового входного сигнала).
4. Автомат переходит в новое состояние \( s' = \delta(s, x) \).

Таким образом, выходной сигнал «запаздывает» на один такт относительно изменения входного сигнала: он остаётся неизменным в течение всего такта, пока автомат находится в данном состоянии, и меняется только при переходе в другое состояние.

Способы задания

Автомат Мура может быть задан несколькими способами:

• Таблица переходов и выходов: таблица, где строки соответствуют состояниям, столбцы — входным сигналам. В ячейках указывается следующее состояние, а отдельный столбец или строка — выходной сигнал для каждого состояния.
• Граф переходов: ориентированный граф, вершины которого — состояния, а дуги — переходы, помеченные входными сигналами. Внутри каждой вершины (или рядом с ней) указывается выходной сигнал, соответствующий этому состоянию.
• Матрица переходов: квадратная матрица, где элементы — множества входных сигналов, вызывающих переход из одного состояния в другое.
• Функциональная схема: в цифровой электронике автомат Мура реализуется с помощью триггеров (регистров состояний) и комбинационной логики, формирующей функции переходов и выходов.

Сравнение с автоматом Мили

Примеры

Пример 1: Детектор последовательности «101»

Рассмотрим автомат Мура, который выдает единицу на выходе, если на вход поступила последовательность «101». Выходной сигнал равен 1 только в состоянии, которое соответствует успешному обнаружению последовательности. Состояния:

• \( s_0 \) (начальное, выход 0): ничего не обнаружено.
• \( s_1 \) (выход 0): получена «1».
• \( s_2 \) (выход 0): получена «10».
• \( s_3 \) (выход 1): получена «101».

Пример 2: Управление светофором

Автомат Мура может управлять простым светофором с двумя состояниями: «Красный» (выход: красный свет) и «Зелёный» (выход: зелёный свет). Переходы происходят по таймеру (входной сигнал «тайм-аут»). Выход однозначно определяется состоянием.

Применение

Автоматы Мура находят применение в различных областях:

• Цифровая схемотехника: проектирование синхронных цифровых схем, таких как контроллеры памяти, процессорные блоки управления, интерфейсные модули. Благодаря предсказуемости выходов, автоматы Мура удобны для реализации на ПЛИС и в заказных микросхемах.
• Программирование: реализация конечных автоматов в программном обеспечении, например, в системах управления базами данных (парсеры SQL), протоколах передачи данных (TCP/IP), игровых движках (состояния персонажа), встраиваемых системах.
• Робототехника и автоматизация: построение систем управления, где реакция на внешние события должна быть детерминированной и не зависеть от случайных помех на входе.
• Лингвистика и обработка текста: автоматы Мура используются в лексическом анализе (токенизация) и в некоторых моделях морфологического анализа.

Критика и ограничения

Основной недостаток автомата Мура — потенциально большее количество состояний по сравнению с автоматом Мили для решения одной и той же задачи. Это может приводить к увеличению объёма памяти (регистров) и усложнению схемы в целом. Кроме того, в некоторых приложениях требуется реакция на входной сигнал в том же такте, что невозможно в чистом автомате Мура. В таких случаях разработчики часто используют автомат Мили или гибридные схемы.

Интересные факты

• Эдвард Мур также известен как один из авторов «закона Мура» (в области интегральных схем), но это другой учёный — Гордон Мур, сооснователь Intel. Эдвард Мур занимался теорией автоматов и искусственным интеллектом.
• Автомат Мура является частным случаем автомата Мили, если дополнить функцию выходов фиктивной зависимостью от входа. Однако на практике эти модели считаются различными из-за разных свойств синхронизации.
• В современных САПР (системах автоматизированного проектирования) цифровых схем часто предлагается автоматическая конвертация автомата Мили в автомат Мура и обратно для оптимизации схемы.

Источники

• Moore, E. F. (1956). «Gedanken-experiments on Sequential Machines». Annals of Mathematics Studies, 34, 129–153.
• Хопкрофт, Дж., Мотвани, Р., Ульман, Дж. (2001). Введение в теорию автоматов, языков и вычислений. 2-е изд. — М.: Вильямс.
• Кох, М. (2015). Цифровая схемотехника: архитектура и проектирование. — СПб.: БХВ-Петербург.
• Справочник по конечным автоматам: «Moore Machine» — статья в электронной энциклопедии Wikipedia (англ. версия).