Введение

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

История

Машина Мели названа в честь Джорджа Х. Мели, который представил эту концепцию в статье 1955 года «Метод синтеза последовательных схем».

Диаграмма

Диаграмма состояний машины Мели связывает выходное значение с каждым ребром перехода, в отличие от диаграммы состояний машины Мура, которая связывает выходное значение с каждым состоянием. Когда входной и выходной алфавиты совпадают и равны Σ, можно также сопоставить автомату Мели ориентированный граф Helix (S × Σ, (x, i) → (T(x, i), G(x, i))). Вершинами этого графа являются пары состояния и символа, каждый узел имеет исходящую степень один, а преемником (x, i) является следующее состояние автомата и символ, который автомат выдает, находясь в состоянии x и считывая символ i. Если автомат является биобратимым, этот граф представляет собой объединение непересекающихся циклов.

Простая

У простой машины Мели есть один вход и один выход. Каждый дуга перехода помечена значением входа (показано красным цветом) и значением выхода (показано синим цветом). Машина начинает работу в состоянии Si. (В этом примере выход представляет собой логическое исключающее ИЛИ двух последних значений входа; таким образом, машина реализует детектор фронта, выдавая 1 каждый раз, когда вход изменяется, и 0 в противном случае.)

Комплексный

Более сложные машины Мили могут иметь несколько входов и несколько выходов.