Автомат Мили

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

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

Формально автомат Мили задаётся как упорядоченная шестёрка множеств и функций:

• S — конечное множество состояний.
• X — конечное множество входных сигналов (входной алфавит).
• Y — конечное множество выходных сигналов (выходной алфавит).
• δ — функция переходов: S × X → S. Она определяет следующее состояние автомата в зависимости от текущего состояния и входного сигнала.
• λ — функция выходов: S × X → Y. Она определяет выходной сигнал в зависимости от текущего состояния и входного сигнала.
• s₀ — начальное состояние: s₀ ∈ S.

Работа автомата Мили происходит в дискретные моменты времени (такты). В каждом такте автомат получает входной сигнал, вычисляет на его основе и текущего состояния выходной сигнал, а затем переходит в новое состояние.

Отличия от автомата Мура

Основное различие между автоматами Мили и Мура заключается в зависимости выходного сигнала.

Автомат Мили может быть преобразован в эквивалентный автомат Мура и наоборот. Однако при таком преобразовании количество состояний может измениться. В общем случае, автомат Мили требует меньше состояний, чем эквивалентный ему автомат Мура.

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

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

Табличный способ

Задаётся двумя таблицами: таблицей переходов и таблицей выходов. В таблице переходов на пересечении строки (текущее состояние) и столбца (входной сигнал) указывается следующее состояние. В таблице выходов на пересечении строки и столбца указывается выходной сигнал.

Графический способ (граф переходов)

Автомат представляется в виде ориентированного графа. Вершины графа соответствуют состояниям автомата, а рёбра — переходам между ними. Каждое ребро помечается парой «входной сигнал / выходной сигнал». Например, метка «x / y» означает, что при подаче на вход сигнала x автомат выдаёт на выходе сигнал y и переходит в новое состояние.

Матричный способ

Автомат задаётся с помощью матриц переходов и выходов, где элементами являются множества входных сигналов, вызывающих соответствующий переход, и соответствующие им выходные сигналы.

Применение

Автомат Мили находит широкое применение в различных областях вычислительной техники и программирования:

• Проектирование цифровых устройств: Синтез конечных автоматов для управления работой процессоров, контроллеров, микросхем памяти и периферийных устройств.
• Разработка протоколов связи: Реализация протоколов передачи данных, где реакция на принятый пакет (выход) зависит от текущего состояния соединения и содержимого пакета (вход).
• Компиляторы и лексический анализ: Построение лексических анализаторов, которые распознают токены (ключевые слова, идентификаторы, числа) на основе последовательности символов. Выходом может быть тип токена или код ошибки.
• Управляющие программы: Реализация логики работы сложных устройств (например, стиральных машин, лифтов, станков с ЧПУ), где последовательность действий зависит от текущего режима и внешних сигналов (датчиков).
• Обработка текста и строк: Реализация алгоритмов поиска подстрок (например, алгоритм Кнута — Морриса — Пратта), где выходом является факт обнаружения совпадения.

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

Преимущества

• Экономия состояний: Как правило, для реализации одной и той же функции требуется меньше состояний по сравнению с автоматом Мура.
• Быстродействие: Выходной сигнал может формироваться без задержки на такт, что позволяет быстрее реагировать на изменение входных данных.

Недостатки

• Чувствительность к гонкам: В комбинационных схемах, реализующих функцию выходов, могут возникать ложные импульсы (глитчи) при изменении входных сигналов, что требует дополнительных мер по синхронизации.
• Сложность анализа: Поведение автомата Мили может быть менее очевидным при отладке, так как выход привязан к переходу, а не к состоянию.
• Зависимость от входов: Выходной сигнал может изменяться при изменении входа, даже если состояние не меняется, что иногда нежелательно.

История

Теория конечных автоматов была разработана в середине XX века. Модель, названная в честь Джорджа Мили (George H. Mealy), была предложена им в 1955 году в статье «A Method for Synthesizing Sequential Circuits» (Метод синтеза последовательных схем). Мили работал в компании Bell Labs. Его модель стала альтернативой более ранней модели Эдварда Мура (Edward F. Moore), предложенной в 1956 году. Обе модели являются фундаментальными для теории автоматов и используются до сих пор.

Источники

1. Дж. Хопкрофт, Р. Мотвани, Дж. Ульман. «Введение в теорию автоматов, языков и вычислений». — М.: Вильямс, 2002. — 528 с.
2. С. А. Майоров, Г. И. Новиков. «Основы теории вычислительных систем». — М.: Высшая школа, 1978. — 408 с.
3. Э. Ульман. «Теория синтаксического анализа, перевода и компиляции». Том 1. — М.: Мир, 1978. — 614 с.