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

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

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

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

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

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

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

${\displaystyle S}$ / ${\displaystyle X}$	${\displaystyle C_{1}}$	${\displaystyle C_{2}}$	${\displaystyle C_{3}}$
q 1	q 1 / S	q 2 / U 1	q 3 / U 2
q 2	q 1 / D 1	q 2 / S	q 3 / U 1
q 3	q 1 / D 2	q 2 / D 1	q 3 / S

Легенда

• ${\displaystyle C_{i}}$ — Входные символы;
• ${\displaystyle q_{i}}$ — Внутренние состояния
• ${\displaystyle U_{i}}$ , ${\displaystyle D_{i}}$ , ${\displaystyle S}$ — Выходные символы.
• ${\displaystyle q_{i}}$ / ${\displaystyle S}$ — функция перехода

См. также

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

Литература

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