Автоматы Мура и Мили: отличия, формулы и примеры

Конечный автомат - это математическая модель устройства, которое читает входные символы по одному, переходит между конечным числом состояний и выдаёт выходные символы. Два классических типа таких автоматов - автомат Мили и автомат Мура - отличаются ровно одним: тем, от чего зависит выход. У Мили выход определяется парой «состояние плюс входной символ» и приписан к дуге перехода, у Мура выход зависит только от состояния и приписан к самому состоянию. Это маленькое различие тянет за собой всё остальное: число состояний, длину выходной строки и удобство построения схемы. Ниже разберём оба типа на одном живом примере - распознавателе подстроки «11» - выведем формулы функций выхода, покажем граф и таблицу переходов и объясним частые ошибки. Чтобы сразу почувствовать разницу, переключите тип автомата в калькуляторе ниже и проследите, как меняется выходная дорожка.

Что такое конечный автомат

Формально конечный автомат с выходом задаётся набором из шести элементов: множество состояний $Q$, входной алфавит $\Sigma$, выходной алфавит $\Delta$, функция переходов $\delta$, функция выхода и начальное состояние $q_0$. Функция переходов одинакова у обоих типов: $\delta : Q \times \Sigma \to Q$ говорит, в какое состояние перейти из текущего по прочитанному символу. Различие только в функции выхода.

Рассчитать для своей задачи

Для распознавателя подстроки «11» вход и выход двоичные: $\Sigma = \Delta = \{0, 1\}$. Выход 1 означает «только что прочитаны две единицы подряд». Автомату достаточно помнить, была ли предыдущая буква единицей, поэтому базовых состояний всего два: $S_0$ - предыдущий символ не единица (или это начало строки), и $S_1$ - предыдущий символ был единицей.

Автомат Мили: выход на дуге

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

$\lambda : Q \times \Sigma \to \Delta.$

Это значит, что выход «привязан» к переходу: одна и та же дуга всегда даёт один и тот же символ. Для нашего распознавателя нужны всего два состояния. Переходы и выходы такие:

$$\begin{aligned} S_0 \xrightarrow{\,0\,/\,0\,} S_0, \quad & S_0 \xrightarrow{\,1\,/\,0\,} S_1, \\ S_1 \xrightarrow{\,0\,/\,0\,} S_0, \quad & S_1 \xrightarrow{\,1\,/\,1\,} S_1. \end{aligned}$$

Запись на дуге читается как «вход / выход». Единица выдаётся ровно на одной дуге - $S_1 \xrightarrow{1/1} S_1$, когда автомат уже находится в $S_1$ (предыдущая буква была единицей) и приходит ещё одна единица. Именно в этот такт замечена пара «11». Длина выходной строки у автомата Мили всегда равна длине входной строки: один прочитанный символ - один выданный.

Рассчитать для своей задачи

Автомат Мура: выход в состоянии

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

$\omega : Q \to \Delta.$

Выход теперь нельзя «спрятать» на конкретной дуге - он определяется тем, где автомат оказался. Поэтому двух состояний уже не хватает: состояние $S_1$ означает «предыдущая буква единица», но из него по единице нужно выдать 1, а из него же по нулю - 0, а выход не может зависеть от входа. Решение - добавить третье состояние $S_2$ с выходом 1, в которое автомат попадает ровно тогда, когда замечена пара «11»:

$\omega(S_0) = 0, \qquad \omega(S_1) = 0, \qquad \omega(S_2) = 1.$

Переходы при этом устроены так, что по единице из $S_1$ или $S_2$ автомат идёт в $S_2$, а по нулю из любого состояния - в $S_0$. Есть и вторая особенность: автомат Мура выдаёт символ выхода стартового состояния ещё до чтения первого символа входа. Поэтому при входной строке длины $n$ выходная строка имеет длину $n + 1$. Это хорошо видно в калькуляторе: переключите тип на «автомат Мура» - дорожка выхода станет на одну клетку длиннее и сдвинется относительно входа.

Граф состояний и таблица переходов

Граф состояний - это ориентированный граф: вершины это состояния, дуги это переходы, помеченные входными символами. У Мили на дугу добавляют ещё и выход через дробь, у Мура выход пишут внутри вершины. Состояние-акцептор (с выходом 1) часто рисуют двойным кружком. Тот же автомат удобно задать таблицей переходов. Для автомата Мили:

В ячейке стоит «следующее состояние / выход». Для автомата Мура выход выносят в отдельный столбец, потому что он не зависит от входа:

Граф и таблица - две записи одного и того же автомата; в задачах обычно требуют обе.

Преобразование Мили в Мур и обратно

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

При переходе от Мили к Муру выход с дуги «вносят» внутрь состояния. Если в состояние входят дуги с разными выходами, его приходится расщепить на несколько копий - по одной на каждое значение выхода. Поэтому число состояний у Мура обычно больше или равно числу состояний у Мили (в нашем примере было 2, стало 3). Обратно, при переходе от Мура к Мили выход состояния переносят на все входящие в него дуги, и лишние состояния часто можно слить - автомат Мили компактнее.

Рассчитать для своей задачи

Практический вывод: Мили обычно требует меньше состояний и реагирует на вход в тот же такт, поэтому удобен для компактных распознавателей. Мур проще проектировать аппаратно - выход снимается прямо с регистра состояния и не «дёргается» в середине такта, что важно для синхронных цифровых схем.

Частые ошибки

• Считать, что выходные строки совпадают посимвольно. У Мура выход на один символ длиннее: первый символ это выход стартового состояния до чтения входа. Значимая часть совпадает, но строки сдвинуты на такт.
• Пытаться построить Мур с тем же числом состояний, что у Мили. Если в одно состояние входят дуги с разными выходами, его обязательно нужно расщепить - иначе выход в состоянии определить нельзя.
• Писать выход у Мура на дуге. У Мура выход приписан только к состоянию. Метка на дуге это лишь входной символ.
• Забывать про начальный выход у Мура. Автомат Мура выдаёт символ ещё до первого входа - это часть выходной строки, его нельзя пропускать.
• Путать функцию переходов и функцию выхода. Переходы $\delta$ у обоих типов одинаковы; различается только функция выхода ($\lambda$ против $\omega$).

FAQ

Чем автомат Мили отличается от автомата Мура? У Мили выход зависит от состояния и входного символа и стоит на дуге перехода ($\lambda(q, x)$). У Мура выход зависит только от состояния и стоит в вершине ($\omega(q)$). Из-за этого Мур обычно требует больше состояний, а его выходная строка на один символ длиннее.

Можно ли любой автомат Мили преобразовать в автомат Мура? Да. Оба типа эквивалентны по выразительной силе. При преобразовании выход переносят с дуг в состояния, при необходимости расщепляя состояния с разными выходами входящих дуг, поэтому число состояний может вырасти.

Почему у автомата Мура выходная строка длиннее, чем у Мили? Мур выдаёт выход стартового состояния ещё до чтения первого символа, поэтому при входе длины $n$ получается $n + 1$ выходных символов. У Мили каждый прочитанный символ даёт ровно один выходной, и длины совпадают.

Коротко

Автоматы Мура и Мили различаются только функцией выхода: у Мили выход $\lambda(q, x)$ зависит от состояния и входа и стоит на дуге, у Мура выход $\omega(q)$ зависит лишь от состояния и стоит в вершине. Из-за этого Мур обычно требует больше состояний и выдаёт строку на символ длиннее (есть выход стартового состояния). Функция переходов у обоих одинакова, а сами автоматы эквивалентны и преобразуются друг в друга. Граф состояний и таблица переходов - две равноправные записи одного автомата, которые в задачах требуют составить вместе.