Конечные автоматы (Finite State Machine): модель Мили/Мура

1. Введение: что такое конечный автомат

Конечный автомат (КА, FSM — Finite State Machine) — математическая модель дискретного устройства с конечным числом состояний, которое:

• в каждый момент находится в одном из состояний;
• переходит между состояниями по определённым правилам (переходам);
• реагирует на входные сигналы и формирует выходные.

Ключевые свойства:

• конечное число состояний (S = {s₀, s₁, …, sₙ₋₁});
• дискретные такты времени (синхронные КА) или асинхронные события;
• детерминированность (для детерминированных КА): из одного состояния при одном входе — один переход.

Области применения:

• проектирование цифровых схем (контроллеры, протоколы);
• анализ и генерация языков (лексические анализаторы);
• моделирование поведения систем (протоколы связи, игровые ИИ);
• синтез автоматов на ПЛИС (FPGA).

2. Основные компоненты модели КА

1. Состояния (states) — вершины графа, описывающие «режим» системы.
2. Входные сигналы (inputs) — внешние воздействия, инициирующие переходы.
3. Выходные сигналы (outputs) — реакция автомата.
4. Функция переходов (δ): S × I → S — определяет следующее состояние.
5. Функция выходов (λ): S × I → O (для Мили) или S → O (для Мура) — формирует выход.
6. Начальное состояние (s₀) — стартовая точка работы.

3. Общая классификация КА

• Детерминированные (DFA) vs недетерминированные (NFA).
• Синхронные (тактируемые) vs асинхронные.
• Автоматы без выхода (распознаватели) vs с выходом (генераторы).
• По способу формирования выхода: модели Мили (Mealy) и Мура (Moore).

4. Модель Мили (Mealy Machine)

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

В автомате Мили выходной сигнал зависит от текущего состояния и входного сигнала:

λ:S×I→O.

Особенности:

• выход может меняться в течение такта при изменении входа;
• переходы на графе помечены входными и выходными сигналами: вход/выход;
• более компактная реализация (меньше состояний), но возможны «гонки» выходов.

4.2. Пример графа переходов

Пусть:

• состояния: S = {A, B};
• входы: I = {0, 1};
• выходы: O = {0, 1}.

Граф:

A --(0/0)--> A  
A --(1/1)--> B  
B --(0/1)--> A  
B --(1/0)--> B

Поведение:

• В состоянии A при входе 0 → выход 0, остаёмся в A.
• В состоянии A при входе 1 → выход 1, переходим в B.

4.3. Таблица переходов и выходов (Mealy)

Текущее состояние	Вход	Следующее состояние	Выход
A	0	A	0
A	1	B	1
B	0	A	1
B	1	B	0

4.4. Преимущества и недостатки

Плюсы:

• меньшее число состояний для той же функциональности;
• быстрая реакция на вход (выход меняется сразу).

Минусы:

• возможные кратковременные ложные выходы («glitches») при смене входа;
• сложнее анализ временных характеристик.

5. Модель Мура (Moore Machine)

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

В автомате Мура выходной сигнал зависит только от текущего состояния:

λ:S→O.

Особенности:

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

5.2. Пример графа переходов

Те же состояния и входы, но выходы привязаны к состояниям:

• A → выход 0;
• B → выход 1.

Граф (переходы без выхода):

A --(0)--> A  
A --(1)--> B  
B --(0)--> A  
B --(1)--> B

Поведение:

• В A выход всегда 0, независимо от входа.
• Переход в B происходит по входу 1, и тогда выход становится 1.

5.3. Таблица переходов и выходов (Moore)

Текущее состояние	Выход	Вход	Следующее состояние
A	0	0	A
A	0	1	B
B	1	0	A
B	1	1	B

5.4. Преимущества и недостатки

Плюсы:

• стабильные выходы (нет «glitches» при смене входа);
• проще анализ временных диаграмм;
• естественная модель для многих физических систем.

Минусы:

• может потребоваться больше состояний (чтобы закодировать разные выходы);
• задержка реакции: выход меняется только после перехода.

6. Сравнение Мили и Мура

Параметр	Мили	Мура
Зависимость выхода	от состояния и входа	только от состояния
Скорость реакции	мгновенная	с задержкой на такт
Число состояний	обычно меньше	может быть больше
Ложные выходы	возможны	исключены
Графическое представление	переход: вход/выход	выход внутри состояния
Типичные применения	протоколы, контроллеры с быстрой реакцией	счётчики, таймеры, последовательные схемы

Важно: любой автомат Мили можно преобразовать в эквивалентный автомат Мура (и наоборот), но при этом может измениться число состояний и временные характеристики.

7. Синтез КА: основные шаги

1. Формализация задачи — описание поведения словами/таблицами.
2. Определение состояний и их кодирование (двоичное, одноместное и др.).
3. Построение графа переходов (с метками входов/выходов).
4. Составление таблиц переходов и выходов (для Мили или Мура).
5. Минимизация числа состояний (если возможно).
6. Кодирование состояний (выбор кода для каждого sᵢ).
7. Синтез логических функций для переходов и выходов (например, на D‑триггерах).
8. Реализация схемы (на логических элементах, ПЛИС).

8. Примеры применения

8.1. Контроллер светофора

• Состояния: «Красный», «Жёлтый», «Зелёный».
• Входы: таймер, датчик движения.
• Выходы: сигналы ламп.
• Модель Мура: выход (цвет) однозначно определяется состоянием.

8.2. Протокол обмена данными

• Состояния: «Ожидание», «Приём байта», «Проверка CRC».
• Входы: биты данных, сигналы готовности.
• Выходы: команды устройствам.
• Модель Мили: выход может зависеть от текущего бита и состояния.

8.3. Кодовый замок

• Состояния: последовательность введённых цифр.
• Вход: цифра с клавиатуры.
• Выход: «Открыто»/«Ошибка».
• Может быть реализован как Мили или Мура в зависимости от требований к задержкам.

9. Реализация на практике

9.1. На логических элементах

• Память состояний: D‑ или JK‑триггеры.
• Логика переходов: комбинационные схемы (дешифраторы, мультиплексоры).
• Логика выходов: для Мили — зависит от Q и X, для Мура — только от Q.

9.2. На ПЛИС (FPGA)

• Описание на VHDL