Автомат Мили

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

Автомат Мили — совокупность [math]\displaystyle{ \boldsymbol{A = (S, X, Y,\delta,\lambda,S_0)} }[/math], где

[math]\displaystyle{ S }[/math] — конечное непустое множество состояний автомата;
[math]\displaystyle{ X }[/math] — конечное непустое множество входных символов;
[math]\displaystyle{ Y }[/math] — конечное непустое множество выходных символов;
[math]\displaystyle{ \delta : S \times X \rightarrow S }[/math] — функция переходов, отображающая пары состояние/входной символ на соответствующее следующее состояние;
[math]\displaystyle{ \lambda : S \times X \rightarrow Y }[/math] — функция выходов, отображающая пары состояние/входной символ на соответствующий выходной символ;
[math]\displaystyle{ S_0\in S }[/math] — начальное состояние.

Кодировка автомата Мили:

Вершина (операторная или логическая), стоящая после вершины «Начало», а также вход вершины «Конец» помечается символом S₁, вершины, стоящие после операторных помечаются символом S_n (n=2,3..).

Представление

Матрица функций переходов

[math]\displaystyle{ S }[/math] / [math]\displaystyle{ X }[/math]	[math]\displaystyle{ C_1 }[/math]	[math]\displaystyle{ C_2 }[/math]	[math]\displaystyle{ C_3 }[/math]
q₁	q₁ / S	q₂ / U₁	q₃ / U₂
q₂	q₁ / D₁	q₂ / S	q₃ / U₁
q₃	q₁ / D₂	q₂ / D₁	q₃ / S

Легенда

[math]\displaystyle{ C_i }[/math] — Входные символы;
[math]\displaystyle{ q_i }[/math] — Внутренние состояния
[math]\displaystyle{ U_i }[/math], [math]\displaystyle{ D_i }[/math], [math]\displaystyle{ S }[/math] — Выходные символы.
[math]\displaystyle{ q_i }[/math] / [math]\displaystyle{ S }[/math] — функция перехода

См. также

JFLAP кроссплатформенная программа симулятор автоматов, машины Тьюринга, грамматик, рисует граф автомата
Автомат Мура в сравнении с автоматом Мили
Автомат Мура

Литература

Mealy, George H. A Method to Synthesizing Sequential Circuits (англ.). — Bell Systems Technical Journal, 1955. — P. 1045—1079. (англ.)
Roth, Charles H., Jr. Fundamentals of Logic Design (англ.). — Thomson-Engineering, 2004. — P. 364—367. — ISBN 0534378048. (англ.)